백준 10517 c++ "Radar Coverage" -PlusUltraCode-

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

 

[필자 사고]

필자는 이 문제를 최소외접원 알고리즘을 이용하여 문제를 해결했다.

ratio는 0.995 로 잡았고 iteration 은 30000으로 잡아 경사하강법 원리를 이용하여 천천히 진행했다.

[코드 해설]

전역 변수와 데이터 구조

• 이 코드에서는 세 점의 좌표를 저장하기 위해 두 개의 전역 벡터 a와 b를 사용합니다.
  • a: 세 점의 X 좌표를 저장.
  • b: 세 점의 Y 좌표를 저장.
• N은 테스트 케이스의 개수를 나타내는 전역 변수입니다.

---

•  

---

3. 테스트 케이스 처리: Game_Start 함수

이 함수는 한 테스트 케이스의 중심 좌표를 계산하고 출력하는 역할을 합니다. 주요 과정은 다음과 같습니다:

1) 데이터 초기화 및 입력

• a와 b를 초기화하고, 세 점의 X, Y 좌표를 입력받습니다.
• 각각 세 점의 X 좌표를 a에, Y 좌표를 b에 저장합니다.

2) 초기 중심 좌표 계산

• 세 점의 평균 좌표를 초기 중심으로 설정합니다.
  • x=합계(a)3,y=합계(b)3x = \frac{\text{합계}(a)}{3}, y = \frac{\text{합계}(b)}{3}x=3합계(a)​,y=3합계(b)​
  • 이를 통해 중심 좌표를 대략적으로 계산한 뒤 세부 조정을 시작합니다.

3) 시뮬레이션 반복 (좌표 조정)

• 중심 좌표 (x, y)를 세 점과의 거리를 기반으로 반복적으로 조정합니다.
  • 중심에서 가장 멀리 떨어진 점을 계산합니다.
  • 그 점을 중심 쪽으로 가까워지도록 비율(ratio)에 따라 조정합니다.
  • 조정 비율은 매 반복마다 줄어들어 점진적으로 세부적인 조정을 수행합니다.

4) 결과 출력

• 최적화된 중심 좌표를 소수점 두 자리로 출력합니다.
• 출력 형식은 "Case #n: x y"로 테스트 케이스 번호와 중심 좌표를 나타냅니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
using namespace std;

vector<double> a, b;
int N;

double calDistance(double x1, double y1,  double x2, double y2 ) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

void Game_Start(int count) {
	a.clear();
	b.clear();


	a.resize(3);
	b.resize(3);
;

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

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

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

		for (int k = 1; k < 3; k++) {
			double curDistance = calDistance(x, y, a[k], b[k]);
			if (maxDistance < curDistance) {
				maxDistance = curDistance;
				maxIndex = k;
			}
		}

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

		ratio *= 0.995;
	}

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

	cout << "Case #" << count << ": " << x << " " << y << '\n';
	
}
int main(void) {
	int count = 1;
	cin >> N;
	for (int i = 0; i < N; i++) {
		Game_Start(i + 1);
	}

}