[13326번] Diameter

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

우선 이 문제에서 가장 먼 두점 t1, t2를 잡아본다.

그러면 문제에서 요구하는 답은 t1과 t2의 거리보다 작거나 같게 된다.

이제 t1에 가까운 순서대로 모든 점을 정렬해보자.

그리고 나서 두 그룹으로 점의 집합을 나눠보자.

1~i - 1번까지의 점을 Group1으로, i ~ N번까지의 점을 Group2라고 하면

B[i]라는 배열을 i~N번까지 점에서 Group2가 가질 수 있는 두 점 사이의 최대 거리라 하고 모두 구한다.

그 후 1~i - 1번까지의 Group1의 두점사이의 거리와 이미 구해놓은 B[i]를 이용하여 정답을 구할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <iostream> #include <algorithm> #include <cstdio> #include <cmath>   using namespace std;   int N; int X[5001], Y[5001], A[5001], B[5001];   int dist(int a, int b)  {     return (X[a] - X[b])*(X[a] - X[b]) + (Y[a] - Y[b])*(Y[a] - Y[b]);  }   int main() {     scanf("%d", &N);       for (int i = 1; i <= N; i++)          scanf("%d%d", X + i, Y + i);       int t1 = 1, t2 = 2;       // 가장 먼 두점 잡고 t1, t2에 저장     for (int i = 1; i<N; i++)          for (int j = i + 1; j <= N; j++)          {             if (dist(t1, t2) < dist(i, j))                  t1 = i, t2 = j; // find t1 and t2         }       for (int i = 1; i <= N; i++)          A[i] = i;       // t1을 기준으로 가까운 점 순으로 정렬     sort(A + 1, A + N + 1, [t1](const int &a, const int &b) {         return dist(t1, a) < dist(t1, b);     });       // 1~i : Group 1, i+1 ~ N : Group 2     for (int i = N; i >= 1;  i--) {         B[i] = B[i + 1];          for (int j = i; j <= N; j++)              B[i] = max(B[i], dist(A[i], A[j]));       } // B[i] : i ~ N 까지의 최대 거리     double ans = 2e9; int mx = 0;     for (int i = 1; i<N; i++)      {         for (int j = 1; j<i; j++)              mx = max(mx, dist(A[i], A[j]));           ans = min(ans, sqrt(mx) + sqrt(B[i + 1]));     }     printf("%f\n", ans); }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus