최소외접원.md

2차원 평면위에 있는 점 N개가 주어질 때, 모든 점을 포함하는 가장 작은 원의 지름을 구하는 문제이다.

이 문제는 알고리즘을 통해 정확한 답을 딱 구한다기보단 답에 가까이 다가가는 식으로 풀 수 있다. 즉, 경사하강법으로 풀 수 있다.

경사 하강법은 어떤 함수에 대해 점점 최솟값으로 수렴하게 충분히 많은 횟수만큼 탐색하는 기법이다.

이 문제에서는 가장 먼 점에 조금씩 다가가면서 점점 다가가는 정도를 작게 조정해주면 답으로 수렴한다.

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

#include <iostream>
#include <cmath>
using namespace std;
pair<double, double> point[301];

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

    double xsum = 0.0, ysum = 0.0;
    for (int i=0;i<n;i++) {
        double x, y;
        cin>>x>>y;
        xsum += x;
        ysum += y;
        point[i]={ x, y };
    }

    pair<double, double> dot = { xsum/n, ysum/n };
    double step=0.1;
    double res=0;

    // 제일 먼거랑 조금씩 더 가깝게 조정
    for (int i=0;i<50000;i++) {
        res=0;
        int m=0;
        for (int j=0;j<n;j++) {
            double d = pow(dot.first - point[j].first, 2) + pow(dot.second - point[j].second, 2);
            if (d>res) {
                m=j;
                res=d;
            }
        }
        dot.first += (point[m].first - dot.first) * step;
        dot.second += (point[m].second - dot.second) * step;
        step *= 0.999;
    }
    printf("%.2f\n", sqrt(res)*2);
}