algospot ARCTIC

문제 링크입니다: https://algospot.com/judge/problem/read/ARCTIC

http://jaimemin.tistory.com/421?category=985009와 유사하게 이분법을 사용하여 푸는 문제였습니다.

한가지 흠이라면 ARCTIC은 북극이므로 제목을 북극기지로 지었어야했다는 점입니다.

/*

남극에는 N 개의 탐사 기지가 있습니다.남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다.

겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다.

이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다.

모든 탐사 기지에는 똑같은 무전기가 지급됩니다.

탐사 본부가 다른 모든 기지에 연락을 할 수 있기 위해 필요한 무전기의 최소 출력은 얼마일까요 ?

*/

#include <iostream>

#include <vector>

#include <queue>

#include <iomanip>

#include <cmath>

using namespace std;

 

const int MAX = 100;

 

int N; //탐사기지 수

//두 기지 사이의 거리를 미리 계산

double dist[MAX][MAX];

 

//거리 d 이하인 기지들만을 연결했을 때 모든 기지가 연결되는지 여부를 반환한다

bool decision(double d)

{

        vector<bool> visited(N, false);

        visited[0] = true;

        queue<int> q;

        q.push(0);

        int check = 0;

 

        while (!q.empty())

        {

               int here = q.front();

               q.pop();

               ++check;

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

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

                       {

                              visited[there] = true;

                              q.push(there);

                       }

        }

        return check == N;

}

 

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

double optimize(void)

{

        double low = 0, high = 1416.00; //1000√2 ~= 14145...

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

        {

               double mid = (low + high) / 2;

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

               if (decision(mid))

                       high = mid;

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

               else

                       low = mid;

        }

        return high;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

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

        {

               cin >> N;

               if (N > MAX)

                       exit(-1);

 

               vector<pair<double, double>> coord;

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

               {

                       double y, x;

                       cin >> y >> x;

                       coord.push_back(make_pair(y, x));

               }

 

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

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

                       {

                              pair<double, double> point1 = coord[j];

                              pair<double, double> point2 = coord[k];

                              //거리 구하기 공식 √((x2-x1)^2+(y2-y1)^2)

                              dist[j][k] = sqrt((point2.first - point1.first)*(point2.first - point1.first) + (point2.second - point1.second)*(point2.second - point1.second));

                       }

 

               cout << fixed << setprecision(2);

               cout << optimize() << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략