백준 2626 c++ "헬기착륙장" -PlusUltraCode-

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

 

[필자 사고]

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

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

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

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

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

[코드 해설]

1. 입력 처리

• 프로그램은 다음과 같은 데이터를 입력받습니다:
  • N: 점의 개수.
  • a, b: 각각 x좌표와 y좌표를 저장하는 벡터.
• 처리 과정:
  • 사용자로부터 점의 개수 N을 입력받습니다.
  • 이어서 각 점의 (x, y) 좌표를 입력받아 벡터 a와 b에 저장합니다.
  cpp

  복사편집

  cin >> N; a.resize(N); b.resize(N); for (int i = 0; i < N; i++) { cin >> a[i] >> b[i]; }

---

2. 초기화

입력을 처리한 후, (x, y)의 초기값을 계산합니다:

• 초기값은 모든 점의 x좌표와 y좌표의 평균으로 설정됩니다. 이는 점들의 대략적인 중심 위치를 나타냅니다.
  cpp

  복사편집

  double x = accumulate(a.begin(), a.end(), 0.0) / N; double y = accumulate(b.begin(), b.end(), 0.0) / N;

---

3. 반복 알고리즘

이 코드는 반복적인 접근 방식을 사용하여 (x, y)를 최적화합니다. 총 30,000번 반복을 수행하며, 각 반복의 동작은 다음과 같습니다:

1) 변수

• ratio: (x, y)가 움직이는 스텝 크기를 제어하는 비율. 매 반복마다 줄어들며, 값은 처음에 0.1로 시작합니다.
• maxDistance: 현재 (x, y)에서 가장 먼 점까지의 거리.
• maxIndex: 가장 먼 점의 인덱스.

2) 거리 계산 및 이동

• 현재 (x, y)에서 모든 점까지의 거리를 계산하여 가장 먼 점을 찾습니다:
  cpp

  복사편집

  double curDistance = hypot(x - a[k], y - b[k]);
• (x, y)를 가장 먼 점 쪽으로 조금씩 이동시킵니다:
  cpp

  복사편집

  x += (a[maxIndex] - x) * ratio; y += (b[maxIndex] - y) * ratio;
• ratio를 줄여 점점 더 세밀하게 조정하도록 설정합니다:
  cpp

  복사편집

  ratio *= 0.994;

---

4. 결과 출력

반복이 끝난 후:

• 최적화된 (x, y) 좌표를 소수점 3자리까지 출력합니다.
  cpp

  복사편집

  cout.precision(3); cout << fixed << x << " " << y << '\n';
• (x, y)에서 가장 먼 점까지의 거리 maxDistance를 출력합니다.

[소스 코드]

#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 curDistance = hypot(x - a[k], y-b[k]);

			if (curDistance > maxDistance) {
				maxDistance = curDistance;
				maxIndex = k;
			}
		}

		x += (a[maxIndex] - x) * ratio;
		y += (b[maxIndex] - y) * ratio;

		ratio *= 0.994;

	}


	cout.precision(3);
	cout << fixed;

	if (round(x) == 0)x = 0;
	if (round(y) == 0)y = 0;

	cout << x << " " << y << '\n';
	cout << maxDistance;

}