문제 68
가장 먼 두 점
평면 위에 $N$개의 점이 있다. 서로 다른 두 점 사이의 거리의 제곱의 최댓값을 출력하라.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(3 \le N \le 200\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 점의 좌표를 의미하는 두 정수 $x$, $y$가 공백으로 구분되어 주어진다. $(-10^9 \le x, y \le 10^9)$
같은 좌표를 가진 점은 두 번 이상 주어지지 않으며 한 직선 위에 있지 않은 세 점이 존재한다.
출력
서로 다른 두 점 사이의 거리의 제곱의 최댓값을 출력한다.
예제 입력 1
6 0 0 4 0 4 3 0 3 2 1 1 2
예제 출력 1
25
공식 해설
볼록 껍질만 남기기
점 $P$를 고정하고 볼록 껍질의 꼭짓점을 모두 포함하는 중심 $P$의 원판을 생각하자. 원판은 볼록하므로 껍질 내부도 모두 포함한다. 따라서 내부 점보다 $P$에서 멀거나 같은 꼭짓점이 존재한다.
이 성질을 거리의 두 끝점에 차례로 적용하면 가장 먼 쌍을 볼록 껍질의 꼭짓점에서 고를 수 있다. 먼저 Monotone Chain으로 변 위의 중간 점을 제외한 볼록 껍질을 구한다.
반대편 지지점을 함께 움직이기
가장 먼 두 점 각각을 지나며 두 점을 잇는 선분에 수직인 평행선을 그리자. 다른 점이 두 선 사이를 벗어나면 반대쪽 끝점과의 거리가 더 커지므로, 두 선은 볼록 껍질을 양쪽에서 받치는 지지선이다. 이런 반대편 접촉점 쌍들을 회전하는 캘리퍼스로 확인하면 된다.
반시계 방향 껍질을 $P_0,\cdots,P_{h-1}$이라 하자. 각 변 $P_iP_{i+1}$에 대해 이 변으로부터 가장 먼 반대쪽 꼭짓점 $P_j$를 유지한다. 거리는 같은 밑변을 가지는 삼각형의 넓이, 즉 외적의 크기로 비교할 수 있다.
$P_{j+1}$의 넓이가 더 크면 $j$를 다음으로 옮긴다. 더 커지지 않으면 $(P_i,P_j)$와 $(P_{i+1},P_j)$의 거리 제곱을 확인한다. 다음 꼭짓점의 넓이가 같은 경우에는 평행한 반대편 변이 닿은 것이므로 $P_{j+1}$과의 쌍도 확인한다.
변이 껍질을 따라 회전할 때 반대쪽 지지점도 뒤로 돌아가지 않으므로 두 포인터는 각각 한 바퀴만 이동한다. 인덱스는 원형으로 처리한다.
정렬을 포함한 시간복잡도는 $O(N\log N)$, 공간복잡도는 $O(N)$이다. 거리 제곱은 최대 $8\cdot10^{18}$이며 이 정수값을 직접 비교한다. 제곱근을 구할 필요가 없어 반올림 오차를 피할 수 있다.
구현 · 언어별 풀이
C++ 구현
볼록 껍질을 vector에 저장하고 다음 인덱스는 껍질 크기로 나눈 나머지로 구한다. 좌표·외적·거리 제곱은 long long으로 계산한다. 넓이가 같은 반대편 두 꼭짓점도 검사하고, 반대편 인덱스를 매 변마다 처음으로 되돌리지 않는다.
C 구현
hull을 구하고 회전하는 캘리퍼스의 $j$를 이전 위치에서 계속 이동한다. 거리 제곱은 long long으로 최대 $8 \cdot 10^{18}$까지 계산한다. 넓이가 같은 다음 후보도 확인하고 sqrt로 바꾸지 않는다.
Python 구현
정수 외적으로 hull과 캘리퍼스를 구성한다. 거리 제곱을 int로 비교하고 답도 정수로 출력한다. 매 변마다 $j$를 $0$으로 되돌리면 캘리퍼스 순회에 이차 시간이 걸린다.
Java 구현
long 좌표 차로 제곱 거리를 계산한다. 캘리퍼스 인덱스를 유지하고 평행한 대변에서 면적이 같으면 두 후보를 검사한다. Math.sqrt는 필요 없다.
Rust 구현
i64로 외적과 거리 제곱을 계산한다. $j$를 순환 인덱스로 유지하고 넓이가 증가하는 동안만 전진한다. 넓이가 같은 후보의 거리도 비교하며 거리 제곱을 그대로 출력한다.
JavaScript 구현
볼록 껍질의 회전 방향과 캘리퍼스의 넓이 비교는 BigInt 외적으로 처리한다. 두 점 사이 거리 제곱도 같은 타입으로 계산한다.
function distance2(a, b) {
const dx = BigInt(a[0] - b[0]);
const dy = BigInt(a[1] - b[1]);
return dx * dx + dy * dy;
}좌표 차는 Number에서도 정확하지만 제곱합은 최대 $8\cdot10^{18}$이라 안전 정수 범위를 넘는다. 제곱근을 구하거나 결과를 Number로 변환하지 말고 best.toString()을 출력한다.
한 변에서 다음 변으로 넘어갈 때 반대편 점의 인덱스를 유지해야 캘리퍼스 순회가 선형이다. 넓이가 같은 다음 점도 거리 후보로 확인하여 평행한 지지선의 두 끝점을 빠뜨리지 않는다.