백준 9158 c++ "Super Star" -PlusUltraCode-

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

 

[필자 사고]

최소 외접원 문제이다. 이 문제만의 특이한 점은 구형태로 주어졌다는 점이다.

다만 구형태로 주어졌어도 하나의 변수만 는 것뿐 2차원에서 풀던것과 똑같이 풀면된다. 

필자는 이번에 30000번의 iteration으로 설정했고 ratio 는 0.995로 갱신으로 설정해서 답을 구했다

 

[코드 해설]

입력 처리

1. 사용자로부터 점의 개수 N을 입력받습니다.
2. 각 점의 (x, y, z) 좌표를 입력받아 세 개의 벡터 a, b, c에 저장합니다.
   • a는 x좌표, b는 y좌표, c는 z좌표를 저장합니다.
3. 특징:
   • N = 0이면 프로그램이 종료됩니다.

---

3. 초기화

1. 벡터 초기화:
   • 새로운 점을 입력받을 때마다 벡터 a, b, c를 초기화합니다.
2. 초기 중심점 계산:
   • x, y, z축의 좌표 평균을 계산하여 초기 중심점 (x, y, z)를 설정합니다.
   • 초기값은 점들의 중심에 가까운 값을 나타냅니다.

---

•  

---

5. 반복 알고리즘

1. 목적:
   • 중심점을 점진적으로 조정하여 중심점에서 가장 먼 점까지의 거리를 최소화합니다.
2. 반복 횟수:
   • 총 30,000번 반복을 수행합니다.

1) 가장 먼 점 찾기

• 현재 중심점 (x, y, z)에서 모든 점까지의 거리를 계산합니다.
• 가장 먼 점의 거리(maxDistance)와 그 점의 인덱스(maxIndex)를 업데이트합니다.

2) 중심점 이동

•  

3) 이동 비율 감소

• ratio를 0.995로 곱하여 반복할수록 중심점의 이동이 점차 줄어듭니다. 이를 통해 중심점의 위치가 더욱 세밀하게 조정됩니다.

---

6. 결과 출력

1. 반복이 끝난 후:
   • 최종 중심점에서 가장 먼 점까지의 거리 maxDistance를 소수점 다섯 자리까지 출력합니다.
2. 출력 형식:
   • 각 테스트 케이스마다 maxDistance를 출력합니다.

[소스 코드]

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

vector<double> a, b, c;
int N;

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

void Game_Start() {
	a.clear();
	b.clear();
	c.clear();

	a.resize(N);
	b.resize(N);
	c.resize(N);

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

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

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

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

		ratio *= 0.995;
	}

	cout.precision(5);
	cout << fixed;
	cout << maxDistance << '\n';
}
int main(void) {
	while (1) {
		cin >> N;
		if (N == 0)break;
		Game_Start();
	}
	
}