(백준) 2389 – 세상의 중심에서… (C++)

문제

2389호: 세상의 중심에서… (acmicpc.net)

설명

(백준) 4360 – 나무가 아닌 별? (C++) – GreenGroup과 마찬가지로 스위트 스팟을 찾는 것이 관건입니다.

경사하강법을 사용했는데 저번에 풀었던 문제처럼 뭔가 쉽게 풀리지 않아서 시간이 좀 걸렸습니다.

#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
double a(101), b(101);

double distance(double a, double b) {
    return pow(a, 2) + pow(b, 2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    double x = accumulate(a, a + N, 0.0) / N;
    double y = accumulate(b, b + N, 0.0) / N;

    double ratio = 0.1, max_distance, current_distance;
    for (int i = 0; i < 600000; i++) {
        int max_distance_index = 0;
        max_distance = distance(x - a(0), y - b(0));
        for (int j = 1; j < N; j++) {
            current_distance = distance(x - a(j), y - b(j));
            if (max_distance < current_distance) {
                max_distance = current_distance;
                max_distance_index = j;
            }
        }
        x += (a(max_distance_index) - x) * ratio;
        y += (b(max_distance_index) - y) * ratio;
        ratio *= 0.999;
    }

    cout << x << " " << y << " " << sqrt(max_distance);

    return 0;
}