백준 13708 c++ "모든 점을 포함하는 원" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 최소외접원 알고리즘을 이용하여 푸는 문제이다.

c++에서는 두점사이 거리를 구하는 공식을 hypot() 함수로 제공해서 쉽게 풀 수 있다.

최소외접원을 간단하게 말하자면 모든 점을 포함하는 최소크기의 원을 말한다.

필자는 30000번의 수행을 거치고 매 수행마다 ratio를 0.994씩 곱해줘서 조금씩 x와 y좌표를

이동하는 식으로 문제를 해결했다.

[코드 해설]

2. 입력 처리

1. 점의 개수 N을 입력받습니다.
2. 각 점의 (x, y) 좌표를 저장하기 위해 두 개의 벡터 a(x좌표)와 b(y좌표)를 사용합니다.
3. 반복문을 통해 점의 좌표를 입력받아 각 벡터에 저장합니다.

---

3. 초기화

1. 초기 중심점 계산:
   • 모든 점의 x좌표와 y좌표의 평균을 계산하여 초기 중심점 (x, y)를 설정합니다.
   • 초기값은 점들 사이의 대략적인 중심 위치를 나타냅니다.
2. 이동 비율(ratio) 초기화:
   • 중심점 이동의 비율은 0.1로 시작하며, 반복하면서 점차 줄어듭니다.

---

4. 반복 알고리즘

30000번의 반복을 통해 중심점을 최적화합니다.

1) 가장 먼 점 찾기

•  

2) 중심점 이동

• 중심점을 가장 먼 점 쪽으로 이동합니다. 이동 거리는 ratio에 의해 제어됩니다.
• 중심점 이동 공식: x←x+(xfarthest−x)×ratiox \leftarrow x + (x_{\text{farthest}} - x) \times \text{ratio}x←x+(xfarthest​−x)×ratio y←y+(yfarthest−y)×ratioy \leftarrow y + (y_{\text{farthest}} - y) \times \text{ratio}y←y+(yfarthest​−y)×ratio

3) 이동 비율 감소

• ratio를 0.997로 곱하여 반복할수록 중심점의 이동을 점진적으로 줄입니다. 이를 통해 중심점의 위치가 점점 더 세밀하게 조정됩니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

using namespace std;

int N;
vector<int> a;
vector<int> b;

int main(void) {
	cin >> N;
	a.resize(N);
	b.resize(N);

	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i];
	}
	
	double x = accumulate(a.begin(), a.end(), 0.0) / N;
	double y = accumulate(b.begin(), b.end(), 0.0) / N;

	double ratio = 0.1, maxDistance, maxIndex;
	for (int i = 0; i < 30000; i++) {
		maxDistance = hypot(x - a[0], y - b[0]);
		maxIndex = 0;

		for (int k = 1; k < N; k++) {
			double currentDistance = hypot(x - a[k], y - b[k]);
			if (currentDistance > maxDistance) {
				maxDistance = currentDistance;
				maxIndex = k;
			}
		}
		x += (a[maxIndex] - x) * ratio;
		y += (b[maxIndex] - y) * ratio;
		ratio *= 0.997;
	}

	cout.precision(2);
	cout << fixed;
	
	cout << 2 * maxDistance;

}