백준 2389 c++ "세상의 중심에서..." -PlusUltraCode-

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

 

[필자 사고]

이 문제는 최소외접원 알고리즘을 이용하여 푸는 문제이다.

c++에서는 두점사이 거리를 구하는 공식을 hypot() 함수로 제공해서 쉽게 풀 수 있다.

최소외접원을 간단하게 말하자면 모든 점을 포함하는 최소크기의 원을 말한다.

필자는 30000번의 수행을 거치고 매 수행마다 ratio를 0.994씩 곱해줘서 조금씩 x와 y좌표를

이동하는 식으로 문제를 해결했다.

[코드 해설]

2. 입력 처리

1. 먼저 점의 개수를 입력받습니다.
2. 각 점의 (x, y) 좌표를 입력받아 두 개의 리스트(벡터)에 저장합니다.
   • 하나는 x좌표, 다른 하나는 y좌표를 저장합니다.

---

3. 초기화

1. 초기 중심점 계산:
   • 입력된 점들의 x좌표와 y좌표의 평균값을 계산하여 초기 중심점을 설정합니다.
   • 예를 들어, 입력된 점이 (0, 0), (4, 0), (0, 3)인 경우 중심점은 (1.33, 1.0)로 시작합니다.
2. 변수 설정:
   • 중심점 이동의 비율(ratio)은 처음에는 0.2로 설정되며, 반복할수록 점점 줄어듭니다.
   • 반복 과정에서 중심점에서 가장 먼 점의 거리(max_distance)와 그 점의 위치(max_index)를 추적합니다.

---

4. 반복 알고리즘

1. 가장 먼 점 찾기:
   • 현재 중심점에서 모든 점까지의 거리를 계산합니다.
   • 이 중 가장 먼 점을 찾고, 해당 점과 중심점 사이의 거리를 기록합니다.
2. 중심점 업데이트:
   • 중심점을 가장 먼 점 쪽으로 이동합니다. 이동 거리는 ratio로 조정되어 점진적으로 작은 스텝으로 이동하게 됩니다.
   • 예를 들어, 현재 중심점이 (1.33, 1.0)이고 가장 먼 점이 (4, 0)인 경우, 중심점은 (1.33, 1.0)에서 (1.8, 0.8)로 조금 이동합니다.
3. 이동 비율 감소:
   • 중심점이 세밀하게 조정될 수 있도록 ratio를 반복적으로 감소시킵니다. 예를 들어, 0.2 → 0.1994 → 0.1988로 줄어듭니다.
4. 반복 종료:
   • 위 과정을 정해진 횟수(예: 10,000번) 동안 반복합니다. 충분한 반복을 통해 중심점은 점들 사이에서 최적의 위치에 수렴합니다.

 

[소스 코드]

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

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<double> x_coords(N), y_coords(N);
    for (int i = 0; i < N; i++) {
        cin >> x_coords[i] >> y_coords[i];
    }

 
    double center_x = accumulate(x_coords.begin(), x_coords.end(), 0.0) / N;
    double center_y = accumulate(y_coords.begin(), y_coords.end(), 0.0) / N;

    double ratio = 0.2;  
    double max_distance, current_distance;
    int max_index;

    for (int iteration = 0; iteration < 10000; iteration++) {
        max_distance = hypot(center_x - x_coords[0], center_y - y_coords[0]);
        max_index = 0;

        
        for (int i = 1; i < N; i++) {
            current_distance = hypot(center_x - x_coords[i], center_y - y_coords[i]);
            if (current_distance > max_distance) {
                max_distance = current_distance;
                max_index = i;
            }
        }

    
        center_x += (x_coords[max_index] - center_x) * ratio;
        center_y += (y_coords[max_index] - center_y) * ratio;

        
        ratio *= 0.997;
    }

  
  
    cout << center_x << " " << center_y << " " << max_distance << endl;

    return 0;
}