AlgoSpot) ARCTIC

문제 : https://algospot.com/judge/problem/read/ARCTIC

동일한 성능을 가진 무전기로 모든 기지에 연락할떄 무전기 성능을 최소화하는 문제입니다.

이분법과 프림알고리즘 두가지 방법을 이용해서 풀었습니다.

두 기지사이의 거리정보를 미리 계산해서 배열에 넣은후 

이분법에서는 queue를 이용해서 인자로 넣어진값으로 모든 기지에 연락할수있으면 true를 반환하고 아닐시 false를 반환하면서 점점 최적값으로 맞춰갔고

프림알고리즘은 priority_queue를 이용해서 값을 계산했습니다.

100번 반복문을 실행하는이유는 절대오차가 10^-7보다 작게하기위해서입니다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

double dist[101][101];
int N;

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

bool decision(double d) {
	int chk = 0;
	vector visited(N, false);
	queue q;
	q.push(0);
	visited[0] = true;

	while (!q.empty()) {
		int source = q.front();
		q.pop();
		++chk;

		for (int dest = 0; dest < N; ++dest) {
			if (!visited[dest] && dist[source][dest] <= d) {
				q.push(dest);
				visited[dest] = true;
			}
		}
	}

	return (chk == N);
}

double optimize() { // 최적화문제를 결정문제로 바꾸기위해 이분법 이용
	double lo = 0.0, hi = 1500.0;

	for (int i = 0; i < 100; ++i) {
		double mid = (lo + hi) / 2;
		
		if (decision(mid)) hi = mid;
		else lo = mid;
	}

	return lo;
}

double prim() { // prim알고리즘을 이용
	double Max_Range = -1;
	vector visited(N, false);
	priority_queue, vector>, greater>> pq; // min 힙생성

	for (int i = 0; i < N; ++i) pq.push(make_pair(dist[0][i] , i));
	visited[0] = true;
	
	while (!pq.empty()) {
		pair n = pq.top(); pq.pop();
		if (visited[n.second]) continue;
		visited[n.second] = true;
		Max_Range = max(Max_Range, n.first);

		for (int i = 1; i < N; ++i) {
			if (!visited[i]) {
				pq.push(make_pair(dist[n.second][i],i));
			}
		}
	}

	return Max_Range;
}
int main() {
	std::ios::sync_with_stdio(false);
	freopen("test.txt", "r", stdin);

	int C;
	double pos[100][2];
	cin >> C;

	while (C--) {
		memset(dist, 0.0, sizeof(dist));
		memset(pos, 0.0, sizeof(pos));
		cin >> N;
		for (int i = 0; i < N; ++i) {
			cin >> pos[i][0] >> pos[i][1];
		}

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				//if (dist[i][j] == 0.0) continue;
				dist[i][j] = make_dist(pos[i][0], pos[i][1], pos[j][0], pos[j][1]);
				dist[j][i] = dist[i][j];
			}
		}

		cout << fixed << setprecision(2);
		//cout << optimize() << endl;
		cout << prim() << endl;
	}

	return 0;
}