（P1452）给定 \(n\) 个点，求最远点对。 \(n\leq 5\times10^4\) 。
（CF429D）给定 \(n\) 个点，求最近点对。 \(n\leq 10^5\) 。
（P6247）给定 \(n\) 个点，求最近点对和最远点对。 \(n\leq 10^5\) 。
（P1429）给定 \(n\) 个点，求最近点对。 \(n\leq 2\times10^5\) 。
（P7883）给定 \(n\) 个点，求最近点对。 \(n\leq 4\times10^5\) ， \(350ms\) 。
都是随机化思路，从易到难。
- 将点分别按照横纵坐标排序，然后将前 \(1000\) 个和后 \(1000\) 个进行配对，时间复杂度 \(O(n\,log\,n+1000^2)\) 。
- 将点分别按照纵坐标排序，将每个点和自己之后的 \(10\) 个点配对，时间复杂度 \(O(n\,log\,n+10n)\) 。
- 将 1，2 合并即可，时间复杂度 \(O(n\,log\,n+1000^2+10n)\) 。
- 同 2 ，将 \(10\) 改成 \(100\) ，时间复杂度 \(O(n\,log\,n+100n)\) 。
- 将点按照 \(abs(x\times y)\) 排序，取后 \(790\) 个点匹配，时间复杂度 \(O(n\,log\,n+790n)\) 。