Chinese bronze

평면 위 점들의 유클리드 최소 스패닝 트리는 델로네 삼각분할의 간선만 사용해도 구할 수 있다. 따라서 모든 $\binom{N}{2}$개의 간선을 만들 필요가 없다.

먼저 주어진 점들의 델로네 삼각분할을 $O(N \log N)$ 시간에 만든다. 델로네 삼각분할은 평면 그래프이므로 간선 수가 $O(N)$개이다. 이 간선들에 대해 실제 유클리드 거리의 제곱을 기준으로 정렬한 뒤, 크루스칼 알고리즘을 수행하면 된다.

왜 충분한지 보이자. 유클리드 MST의 어떤 간선 $uv$를 잡고, $uv$를 지름으로 하는 원을 생각한다. 이 원 안에 다른 점 $w$가 있다면 $uw$와 $vw$가 모두 $uv$보다 짧다. MST에서 $uv$를 제거해 생기는 두 컴포넌트 중 $w$가 속하지 않은 쪽과 $w$를 잇는 더 짧은 간선으로 바꿀 수 있으므로 모순이다. 따라서 $uv$의 열린 지름원 안에는 다른 점이 없다. 이런 간선은 상대 이웃 그래프의 간선이고, 상대 이웃 그래프는 델로네 그래프에 포함된다. 동거리나 공원점 퇴화가 있는 경우에도 표준적인 미소 perturbation 또는 동률 교환 논증으로 같은 총 가중치의 MST를 델로네 삼각분할 간선들만으로 잡을 수 있다.

좌표가 정수이고 범위가 $10^8$ 이하이므로 방향 판정과 in-circle 판정은 차분을 잡은 뒤 __int128 정수 연산으로 처리할 수 있다. 델로네 간선 수는 $O(N)$개이고, 정렬 및 크루스칼이 $O(N \log N)$ 시간이므로 전체 시간 복잡도는 $O(N \log N)$이다.

Solution written by GPT5.5