- 设 $f(l,r)$ 为分解与合并区间 $[l,r]$ 的函数。
- 设 $g(l,r)$ 为区间 $[l,r]$ 中的最近点对距离。
- 设 $dis(a_i,a_j)=\sqrt{(a_i.x-a_j.x)^2+(a_i.y-a_j.y)^2}$。
二分算法显然易见。
首先，将 $p_i$ 按 $x_i$ 排序。
将区间 $f(l,r)$ 分解为 $f(l,mid)$ 和 $f(mid+1,r)$，其中 $mid$ 为 $l,r$ 的中点。
通过 $f(l,mid)$ 和 $f(mid+1,r)$ 得到最小值 $\delta=\min(g(l,mid),g(mid+1,r))$，有可能 $dis(a_{i\in[l,mid]},a_{j\in[mid+1,r]})<\delta$，即需要算出 $dis(a_{i\in[l,mid]},a_{j\in[mid+1,r]})$，但是如果把所有的距离都算，则会超时，考虑优化。
因为需要寻找 $dis(a_{i\in[l,mid]},a_{j\in[mid+1,r]})<\delta$，既不必查找那些 $dis(a_{i\in[l,mid]},a_{j\in[mid+1,r]})$ 一定大于等于 $\delta$ 的。
考虑怎样排除那些一定不可能的情况，行枚举过了，现在枚举列。首先，将区间 $[l,r]$ 中的 $a_i$ 按 $y$ 排序，设 $midy=\left \lfloor \frac {a_r.y-a_l.y}{2} \right \rfloor$，则将所有 $|a_i.y-midy|<\delta$ 的 $y$ 加入枚举范围，其他的 $a_{i\in[l,r]}$ 直接排除。
设 $a_{i\in[l,mid]}.y=midy-\delta$，$a_{i\in[mid+1,r]}.y=midy$，则 $dis(a_{i\in[l,mid]},a_{j\in[mid+1,r]})$ 定大于等于 $\delta$。
- 若 $a_{i\in[l,mid]}.x=a_{i\in[mid+1,r]}.x$，则 $dis(a_{i\in[l,mid]},a_{j\in[mid+1,r]})=\delta$。
- 若 $a_{i\in[l,mid]}.x\neq a_{i\in[mid+1,r]}.x$，则 $dis(a_{i\in[l,mid]},a_{j\in[mid+1,r]})>\delta$。
显然易见，此时为被排除的最好情况，故排除方法是正确的。
排除好了，怎样比较 $dis(a_{i\in[l,mid]},a_{j\in[mid+1,r]})$，可以使用双指针。
设左指针 $L$，右指针 $R$。
则随着 $R$ 往右移动，$L$ 移动时需满足 $a_R.y-a_L.y\ge \delta$，即此时一定 $dis(a_L,a_R)\ge \delta$，而后面所有的 $R$ 都满足 $dis(a_L,a_R)\ge \delta$，即不满足条件，将$L$ 往右移动。
这样就可以求出最近点对的距离 $\delta$ 了。