남극 기지 :: 알고스팟

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

문제

남극에는 N 개의 탐사 기지가 있습니다. 남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. 탐사 본부가 다른 모든 기지에 연락을 할 수 있기 위해 필요한 무전기의 최소 출력은 얼마일까요?

탐사 본부는 다른 기지를 통해 간접적으로 연락할 수 있다고 가정합니다.

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <queue>

#include <vector>

#include <cmath>

#include <iomanip>

using namespace std;

int N;

double dist[101][101];

double X[101], Y[101];

void precalc()

{

for (int i = 0; i < N; ++i)

{

for (int j = 0; j < N; ++j)

{

if (i == j) continue;

dist[i][j] = sqrt(pow((X[j] - X[i]), 2) + pow((Y[j] - Y[i]), 2));

}

}

}

bool decision(double d)

{

vector<bool> visited(N, false);

visited[0] = true;

queue<int> q;

q.push(0);

int seen = 0;

while (!q.empty())

{

int here = q.front();

q.pop();

++seen;

for (int i = 0; i < N; ++i)

{

if (!visited[i] && dist[here][i] <= d)

{

visited[i] = true;

q.push(i);

}

}

}

return seen == N;

}

// 모든 기지를 연결할 수 있는 최소의 d를 반환한다.

double optimize()

{

double lo = 0, hi = 1416.00;

for (int it = 0; it < 100; ++it)

{

double mid = (lo + hi) / 2;

// mid가 가능하다면, 더 좋은 (작은) 답을 찾는다.

if (decision(mid))

hi = mid;

// mid가 불가능하다면, 더 나쁜 (큰) 답을 찾는다.

else

lo = mid;

}

return hi;

}

int main()

{

int C;

cin >> C;

while (C--)

{

cin >> N;

for (int i = 0; i < N; ++i)

{

cin >> X[i] >> Y[i];

}

precalc();

cout << showpoint << fixed << setprecision(2) << optimize() << "\n";

}

return 0;

}