[2389] 세상의 중심에서...

한줄후기 : 제출 수가 적은건 풀지 말자

 

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

2389번: 세상의 중심에서...

기하 도전.

간단하게 여러 점들이 주어지면 그 점들을 모두 포함하는 가장 작은 원의 중심과 반지름을 구하는 문제이다.

처음에 중심을 각 x좌표 y좌표의 평균으로 두면 되는 것과 그 중심에서 가장 먼 점과의 거리를 반지름으로 구하면 된다고 알았으나.. 그게 구현하기 만만치 않았다. 중심을 구하긴 쉬운데 반지름이 영..

그러다 찾은 다른 분의 코드를 보고 따라 구현해봤다. - Gradient discent 알고리즘 이라고 한다.

 

http://codeforces.com/blog/entry/23554

 

http://ideone.com/vju6Uh  - 참고 사이트

Ideone.com

Smallest Enclosing Circle/Sphere Problem - Codeforces

#include <cstdio>
#include <cmath>
using namespace std;
double distance(double a, double b){
	return a*a+b*b;
}
int main(){
	int n;
	scanf("%d", &n);
	double a[101];
	double b[101];
	double x=0, y=0;
	for(int i=0; i<n; i++){
		scanf("%lf %lf", &a[i], &b[i]);
		x+= a[i];
		y+= b[i];
	}
	x = x/n;
	y = y/n;
	
	double P = 0.1, d,e,f,j;
	for (int i = 0; i < 30000; i++) {
		int f = 0;
		d = distance(x - a[0], y - b[0]);
		for (int j = 1; j < n; j++) {
			e = distance(x - a[j], y - b[j]);
			if (d < e) { d = e; f = j; }
		}
		x += (a[f] - x)*P;
		y += (b[f] - y)*P;
		P *= 0.999;
	}
	printf("%.10f %.10f ",x,y);
	printf("%.10f", sqrt(d));
	return 0;
}

 

어렵다.