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);}