[C++]11930-Smallest Enclosing Sphere

www.acmicpc.net/problem/11930  문제링크다.

11930번: Smallest Enclosing Sphere

밑에는 비슷한 문제들이다.

www.acmicpc.net/problem/2626

2626번: 헬기착륙장

www.acmicpc.net/problem/13708

13708번: 모든 점을 포함하는 원

www.acmicpc.net/problem/2389  

2389번: 세상의 중심에서...

저 문제하나 풀줄알면 밑에 세개는 꽁으로 경험치 먹을 수 있다.

뭐, 보통은 저기 3개중에 하나로 입문하겠지만. 나도 2389번으로 입문했고.

2389번 포스팅 https://ssuallassualla.tistory.com/155

 

2389랑 다를게 없다. z생긴거랑, 출력바뀐거 빼면.

 

2389는 볼록껍질을 사용해서 조금 시간을 줄였는데, c++에서 볼록껍질 해본적도 없고, 만들기 귀찮아서 그냥 했다.

#include <cstdio>
#include <math.h>
#include <utility>

#define ROUNDING(x, dig)	( floor((x) * pow(float(10), dig) + 0.5f) / pow(float(10), dig) )
int n;
double dots[1001][3];
double getDistanceDoubled(double p1[], double p2[]) {
    return (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1]) + (p1[2]-p2[2])*(p1[2]-p2[2]);
}
int main(){
    scanf("%d",&n);
    double x, y, z;
    for(int i=0;i<n;i++){
        scanf("%lf %lf %lf", &x, &y, &z);
        dots[i][0] = x;
        dots[i][1] = y;
        dots[i][2] = z;
    }
    x = 0;
    y = 0;
    z = 0;
    for(int i=0;i<n;i++){
        x += dots[i][0];
        y += dots[i][1];
        z += dots[i][2];
    }
    x /= (double)n;
    y /= (double)n;
    z /= (double)n;
    double ratio = 0.1;
    double maxVal, tmp;
    for(int i = 0; i < 20000; i++) {
        double point[3] = {x,y,z};
        maxVal = 0;
        int maxIn = 0;
        for(int j = 0; j < n; j++) {
            tmp = getDistanceDoubled(point, dots[j]);
            if(tmp > maxVal) {
                maxVal = tmp;
                maxIn = j;
            }
        }
        x += (dots[maxIn][0] - x)*ratio;
        y += (dots[maxIn][1] - y)*ratio;
        z += (dots[maxIn][2] - z)*ratio;
        ratio *= 0.995;
    }
    printf("%.2lf", ROUNDING(sqrt(maxVal),2));
}

밑에 틀린 것은, ratio *= 0.995 말고 0.999를 해서 틀렸다. 매개변수 적당히 잘 찍는 것도 중요한 것 같다.