가장 먼 두 점 구하기

2차원 좌표 평면에 정수 좌표 (x, y)로 이루어진 서로 다른 점 $N$개가 있다고 하자. 이 점들 중 유클리드 거리계에서 가장 먼 두 점을 $O(N \lg N)$ 시간복잡도로 구할 수 있다.

Claim 1) 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양 끝 점의 거리 중 최대값이 가장 먼 두 점의 거리다.

증명) $N$개의 점들 중 가장 먼 두 점을 $a$와 $b$라 하자. $a$와 $b$를 잇는 선분을 그리고 수직한 직선을 그렸을 때 아래와 같이 된다.

파란색 직선 위를 포함하여 파란색 영역에 $a$와 $b$ 이외에 다른 점들은 존재하지 않다. 만약 존재한다고 가정하면 $a$와 $b$가 가장 먼 두 점이라는 가정에 모순된다.

따라서 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양 끝 점의 거리만 고려해도 가장 먼 두 점의 거리를 구할 수 있다.

Lemma 1) 임의의 기울기의 직선에 닿는 양 끝 점은 $N$개의 점을 모두 포함하는 볼록껍데기(Convex Hull)의 꼭지점이다.

Lemma 2) 볼록껍데기의 변들에 해당하는 기울기에 대해서만 고려해도 된다.

Lemma 1은 쉽게 증명된다. Lemma 2는 자세한 증명은 생략하지만, 볼록껍데기의 변들에 해당하는 기울기에 대해서만 고려해도 모든 기울기에 대해 고려할 때와 양 끝 점 쌍은 같게 나온다는 사실을 확인하면 된다. 위 두 lemma가 성립하므로 Graham Scan으로 $O(N \lg N)$ 시간안에 볼록껍데기를 구하고, $O(N)$ 시간안에 가장 먼 두 점을 구할 수 있다.

#include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) typedef long long lld; int N; struct Z{ int x, y; } A[MAXN]; int ccw(int ax, int ay, int bx, int by, int cx, int cy) { lld k = (lld)(bx-ax)*(cy-ay)-(lld)(cx-ax)*(by-ay); if (k > 0) return 1; if (k) return -1; return 0; } int ccw(const Z &a, const Z &b, const Z &c){ return ccw(a.x, a.y, b.x, b.y, c.x, c.y); } lld dist(const Z &a, const Z &b) { return (lld)(b.x-a.x)*(b.x-a.x) + (lld)(b.y-a.y)*(b.y-a.y); } int main() { scanf("%d", &N); for (int i=1;i<=N;i++) scanf("%d%d", &A[i].x, &A[i].y); // Graham Scan for (int i=1;i<=N;i++) if (A[1].y > A[i].y || A[1].y == A[i].y && A[1].x > A[i].x) swap(A[1], A[i]); sort(A+2, A+N+1, [](const Z &a, const Z &b){ int k = ccw(A[1], a, b); if (k) return k > 0; return (a.y-A[1].y)+abs(a.x-A[1].x) < (b.y-A[1].y)+abs(b.x-A[1].x); }); vector <int> stk = {1}; stk.reserve(N); for (int i=2;i<=N;i++){ while (sz(stk) > 1 && ccw(A[stk[sz(stk)-2]], A[stk.back()], A[i]) <= 0) stk.pop_back(); stk.pb(i); } // Farthest two point int j = 1; lld ans = 0; Z p, q; for (int i=0;i<sz(stk);i++){ int ni = (i+1) % sz(stk); for (;;){ int nj = (j+1) % sz(stk); int v = ccw(0, 0, A[stk[ni]].x-A[stk[i]].x, A[stk[ni]].y-A[stk[i]].y, A[stk[nj]].x-A[stk[j]].x, A[stk[nj]].y-A[stk[j]].y); if (v > 0) j = nj; else break; } lld v = dist(A[stk[i]], A[stk[j]]); if (ans < v) ans = v, p = A[stk[i]], q = A[stk[j]]; } printf("Farest two points are (%d, %d) <-> (%d, %d)\n", p.x, p.y, q.x, q.y); }