BOJ 2389 | 세상의 중심에서...

사실 이건 ㄹㅇ 날먹 문제가 맞다.
최소 외접원 계열 문제는 죄다 경사하강법으로 해결이 가능하다.

최소 외접원을 구하기 위해 휴리스틱으로 계속 지워나가면서 푸는 $O(N)$ 알고리즘의 존재는 알고 있다.

근데 내가 그걸 쓸 줄 모르기도 하고, 애초에 최소 외접원 계열 문제는 경사 하강법으로 비효율적이지만 진짜 쉽게 해결이 가능해서 이 방법을 소개해보려고 한다.

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

최소 외접원 문제는 명백하게 최솟값이 존재하고, 극값이 하나인지는 잘 모르겠는데 모든 점들의 평균에서 시작하면 문제없이 최솟값에 잘 걸린다.

직관적으로 한번 생각해보자.

검은색 점들이 주어졌을 때, 그 점들의 평균을 내서 빨간색 점을 구하고, 그 점을 중심으로 하는 점들의 외접원을 구한다.

반지름은 빨간색 점에서 가장 멀리 떨어진 점과 빨간색 점의 거리가 된다.

이 과정은 $O(N)$에 가능하다.

현실의 문제 해결이라면 Convex Hull을 구해서 최적화 하는 것이 효율적이겠지만 테스트 케이스가 모두 Convex Hull로 주어질 수 있기 때문에 문제 해결에 큰 의미는 없다.

가장 멀리 떨어진 점 방향으로 빨강 점이 움직인다고 생각하자.
반지름 길이의 일정 %(퍼센트) 만큼 움직인다.
초기값은 10% 정도로 생각하자.

이렇게 움직이면 빨강 점은 최소 외접원의 중심에 점점 가까워지게 된다.
이제 이 가중치를 점점 줄여나가면서 반복하자.

노란 원이 최소 외접원이고, 노란 점이 최소 외접원의 중심이다.
이제 빨강 점이 어떤 움직임을 보이는지 계속 보자.

점점 빨강 점이 노랑 점으로 수렴하는 것이 보인다.

가중치가 줄어드는 정도에 따라 반복 횟수를 설정해줘야 하고, 가중치는 이전 가중치의 99.99%~99.5%까지 문제에 맞게 잘 설정해주면 된다.

이 방법은 반복 횟수에 따라 시간 초과가 날 수 있으므로 TLE만 주의하자.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Point{
	double x, y;
};

int main(){
	int N; cin >> N;
	vector<Point> fan;
	for (int i = 0; i < N; i++){
		double a, b; cin >> a >> b;
		fan.push_back({a, b});
	}
	
	double w = 0.1;
	Point center = {0, 0};
	
	for (auto &i: fan){
		center.x += i.x/N;
		center.y += i.y/N;
	}
	
	double mxdist, radius = 0;
	Point mnPoint;
	for (int i = 0; i < 1000000; i++){
		// get Radius
		mxdist = 0; Point mxPoint;
		for (auto &i: fan){
			double dist = sqrt((center.x - i.x)*(center.x - i.x)+(center.y - i.y)*(center.y - i.y));
			if (mxdist < dist){
				mxPoint = i; mxdist = dist;
			}
		}
		
		// set center
		center.x = center.x + (mxPoint.x - center.x)*w;
		center.y = center.y + (mxPoint.y - center.y)*w;
		w *= 0.9999;
	}
	
	cout.precision(11);
	cout << center.x << " " << center.y << " " << mxdist; 
}