[13326번] Diameter

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬

2. 구현

문제가 어렵다.

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

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

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

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

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

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

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

소스 코드 : 

#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) { // lambda function
        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 + 1; 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 >>