백준 11930 c++ "Smallest Enclosing Sphere" -PlusUltraCode-

https://www.acmicpc.net/problem/11930

 

[필자 사고]
최소 외접원 문제이다. 이 문제만의 특이한 점은 구형태로 주어졌다는 점이다.

다만 구형태로 주어졌어도 하나의 변수만 는 것뿐 2차원에서 풀던것과 똑같이 풀면된다. 

필자는 이번에 20000번의 iteration으로 설정했고 ratio 는 0.995로 갱신으로 설정해서 답을 구했다.

[코드 해설]

1. 입력 처리

• 먼저 NNN개의 점의 개수를 입력받습니다.
• 각 점의 xxx, yyy, zzz 좌표를 각각 세 개의 벡터 a, b, c에 저장합니다. 이 벡터들은 각각 모든 점의 xxx, yyy, zzz 좌표를 담고 있어 이후 계산에서 활용됩니다.

---

2. 초기 중심점 계산

• 중심점을 구하기 위해 각 좌표의 평균값을 계산합니다.
  • xxx 좌표의 평균은 모든 점의 xxx 좌표를 더한 후 점의 개수 NNN으로 나눈 값입니다.
  • yyy와 zzz 좌표도 동일한 방식으로 계산됩니다.
• 이렇게 계산된 평균값이 중심점의 초기 좌표로 설정됩니다. 이 초기값은 중심점의 대략적인 위치를 빠르게 설정하는 데 사용됩니다.

---

3. 중심점 최적화

• 초기 중심점에서 시작해 모든 점과의 최대 거리가 최소가 되는 방향으로 중심점을 반복적으로 조정합니다.
• 중심점 조정 과정은 다음과 같습니다:
  1. 현재 중심점에서 각 점과의 거리를 계산합니다.
  2. 가장 먼 거리에 있는 점을 찾습니다.
  3. 중심점을 이 가장 먼 점의 방향으로 이동시킵니다. 이때 이동 거리는 점과의 거리의 일정 비율로 설정됩니다.
  4. 이동 비율은 반복이 진행될수록 점차 줄어듭니다. 이를 통해 초기에는 큰 단위로 이동하며 대략적인 중심점을 찾고, 반복이 진행될수록 미세 조정이 이루어지게 됩니다.
• 이 과정은 정해진 횟수(20,000번) 동안 반복됩니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

using namespace std;

int N;
vector<int> a;
vector<int> b;
vector<int> c;

double calculateDistance(double x1, double y1, double z1, double x2, double y2, double z2) {
    return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2) + pow(z2 - z1, 2));
}

int main(void) {
    cin >> N;
    a.resize(N);
    b.resize(N);
    c.resize(N);

    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }


    double x, y, z;
    x = accumulate(a.begin(), a.end(), 0.0) / N;
    y = accumulate(b.begin(), b.end(), 0.0) / N;
    z = accumulate(c.begin(), c.end(), 0.0) / N;

    double ratio = 0.1, maxDistance;
    int maxIndex;

    for (int iter = 0; iter < 20000; iter++) {
        maxDistance = calculateDistance(a[0], b[0], c[0], x, y, z);
        maxIndex = 0;


        for (int k = 1; k < N; k++) {
            double curDistance = calculateDistance(a[k], b[k], c[k], x, y, z);
            if (curDistance > maxDistance) {
                maxDistance = curDistance;
                maxIndex = k;
            }
        }


        x += (a[maxIndex] - x) * ratio;
        y += (b[maxIndex] - y) * ratio;
        z += (c[maxIndex] - z) * ratio;


        ratio *= 0.995;

       
    }

    
    cout.precision(2);
    cout << fixed;
    cout << maxDistance << endl;

    return 0;
}