좌표평면에서 가장 먼 점 찾기

아마 KOI 2016 먼 별 문제로 많은 사람이 알게 된 가장 먼 점 찾기 알고리즘이다.

문제: https://www.acmicpc.net/problem/10254

요약하자면, 2차원 평면상의 점이 N(2≤N≤100,000)개 있을 때, 유클리드 거리가 가장 먼 두 점을 찾으라는 것이다. 이 문제에서 첫 번째로 생각할 수 있는 것은 간단하다.

1. 가장 먼 두 점은 컨벡스 헐 위에 있다.

증명. 그 두 점 A, B 중 하나인 A가 컨벡스 헐 위에 없다고 하자. 그러면 다른 컨벡스 헐 위의 세 점이 있어, 그 세 점으로 이루는 삼각형 안에 A가 들어가게 된다(삼각분할). 그 세 점 모두 B와의 거리가 A보다 작다면 모순이므로, A, B는 가장 먼 점이 아니게 된다.

이제, 컨벡스 헐의 점들을 순서대로 돌면서 가장 먼 점을 찾는 방법을 생각할 수 있다! 두 이터레이터 i, j를 서로 반대편에 있게 한 바퀴 돌리면서 가장 먼 점을 찾아나가고 싶다. 현혹되기 쉬운 반례가 있는 한 방법은, i와 j의 거리가 극대가 될 때까지 j를 이동하는 것이다. 나도 이 방법을 예전에 사용했었고, 오답을 받았다. 증명 가능한 방법은 다음과 같다.

2. 가장 먼 두 점은, 어떤 기울기에 대해 양 끝의 두 점이다.

증명. 특히, 두 점을 잇는 직선에 수직한 기울기에 대해 양 끝이 아니라고 하면, 실제 양 끝 점이 더 멀게 된다.

가능한 기울기들 중에서, 컨벡스 헐의 각 변과 수직한 기울기들에 대해서만 모두 고려해보면 된다. 그렇지 않고 가장 먼 점이 있다고 해도, 그 점은 반대편에서 무조건 고려되기 마련이다. 반대편에서 기울기가 같은(아니면 기울기가 작은 것들 중에 가장 큰) 변을 찾고, 그 변의 양끝 점과의 거리를 고려하면 된다. 이는 변의 벡터를 생각하고, 그 벡터의 외적을 생각하면 된다. 두 벡터의 외적은 다음과 같이 정의된다.

$a \times b = a_x b_y - b_x a_y $

외적이 양수이면 두 벡터가 이루는 각도가 0도 초과 180도 미만이고, 음수이면 -180도 초과 0도 미만이다. ${A}_{i} {A}_{i+1} \times {A}_{j} {A}_{j+1} $가 0 이하가 될 때까지 j를 증가시키고, (i, j)와 (i, j+1) 두 가지 후보( (i, j+1)을 고려하는 이유는, 두 벡터가 평행할 때를 대비해서이다.)들을 계속 고려해주면서 i, j를 앞으로 나아가면 된다. 대략 다음과 같은 코드가 나오게 된다. vect(x)는 ${A}_{x} {A}_{x+1}$의 벡터를 pair로 리턴해주고, point(x)는 컨벡스 헐의 크기가 n일 때 x%n번째 점을 리턴해주는 함수이다.

lint ans = 0;
int a = 0, b = 0;
for (int i=0, j=1; i<n; i++) {
    while (cross(vect(i), vect(j)) > 0) j++;
    for (int k=j; k<j+2; k++) {
        lint d = dist(point(i), point(k));
        if (d > ans) {
            ans = d;
            a = i; b = k;
        }
    }
}