平面最近点对
WeLikeStudying · · 题解
- 人类的智慧不是乱搞。
- 如果那些乱搞的人知道存在正解和乱搞代码一样短会如何感想？
题意
- 链接。
- 给定平面上的
n （n\le 5\times 10^4 ） 个点，求最近点对。
分析
- 我们充分发扬人类智慧，放弃繁杂的分治，将
\text{set} （当然，可重）用到极致。 - 我们先对
x 坐标排序，然后一个一个添加点，与分治类似，我们尝试动态更新，咱们设置一个阈值d 表示目前找到的最优解（初始化其实可以O(1) 随机两个不同的点）。 - 首先
\text{set} 以y 为关键字。 - 每次加入的时候，我们可以把与当前点横坐标差值超过
d 的先扔掉，然后暴力查询纵坐标差不超过d 的点更新d 。 - 显然你卡我的唯一的途径是让我超时，但你没法卡我，因为这个做法复杂度是对的（
O(n\log n) ），有兴趣可以自己证明，如果没兴趣可以看我在下面给出的证明。 - 代码实现，代码长度
\text{900B} ，常数比分治小很多。 - 顺带一提，由于这个不开放数据，我到这道调试，过了那道，然后就过了这道。
证明