13326번: Diameter

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

주어진 점들 중 가장 먼 두 점을 s, e라고 하자. 답이 이 두 점 사이 거리보다 작기 위해선 s와 e가 서로 다른 그룹에 있어야 한다. 각 두 점이 속한 그룹을 S, E라 하자.

s와 e가 각각 중심이 되는 두 원(A, B)을 생각해보자. 이 두 원은 주어진 점들을 모두 포함하고, 각 원주에는 적어도 하나의 점이 존재한다.
이제 각 점들은 두 원과의 포함관계에 따라 다음과 같이 두 그룹으로 나눠질 수 있다.

i) A 안에 존재하고 B 안에 존재하지 않는 경우
S에 포함
ii) B 안에 존재하고 A 안에 존재하지 않는 경우
E에 포함
iii) A, B 안에 존재하는 경우
S 혹은 E 둘 중 아무 그룹에 포함

그런데 A, B가 만나는 경우 답은 A, B 반지름 합 이상이 되며, 이 값은 s와 e 사이 거리 이상이다. 따라서 두 원은 무조건 분리되도록 그려야 한다.

p[i]를 s로 부터 i번째 가까운 점이라고 하자. p[0...j], p[j+1...n-1] 두 그룹으로 나누어 원을 그려보면 j를 조절함에 따라 가능한 분리된 두 원을 모두 그려볼 수 있다.
답은 min( (p[0...j]에서 가장 먼 두 점 거리) + (p[j+1...n-1]에서 가장 먼 두 점 거리) )이 된다.

최종 시간복잡도는 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
#define dis(u,v) ((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]))
int n, pfx, sfx[5000], a[5000], s, e, x[5000], y[5000];
double res = 1e9;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]), a[i] = i;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (dis(s, e) < dis(i, j)) s = i, e = j;
    sort(a, a + n, [](int u, int v) {return dis(s, u) < dis(s, v); });
    for (int i = n - 1; i--;) {
        sfx[i] = sfx[i + 1];
        for (int j = n; --j > i;) sfx[i] = max(sfx[i], dis(a[i], a[j]));
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) pfx = max(pfx, dis(a[i - 1], a[j]));
        res = min(res, sqrt(pfx) + sqrt(sfx[i]));
    }
    printf("%lf", res);
    return 0;
}