平面最近点对

参考资料

• 平面最近点对 - OI Wiki

简介

平面最近点对 问题求 $n$ 个点中距离最小的一对。分治法按 $x$ 坐标把点集二分，递归求左右两半的最近距离 $d$，再只需检查横坐标落在中线左右 $d$ 范围内、且纵坐标相近的点对，整体复杂度 $O(n\log n)$。

例题

洛谷 P1429 平面最近点对（加强版）

给定平面上 $n$ 个点，求距离最近的两个点之间的欧几里得距离。