题解 P1429 【平面最近点对（加强版）】

qwaszx · 2019-01-31 12:02:03 · 题解

有趣的分治呢

暴力的做法就是枚举两个点算距离更新答案

即使这样你也可以优化一下你的暴力

众所周知sqrt是一个跑得极慢的函数

所以我们可以两边平方消掉sqrt，最后再算一次即可

然后看分治做法.当然上面的技巧基本上可以用于带sqrt的所有题目.

先考虑降维打击，如果只有一维怎么做.

把所有点按照坐标排序，然后在中位数的位置画一条线，把点分成两个子集P_1和P_2.

我们只需要算出所有p\in P_1,q\in P_2的min{dis(p,q)}，然后递归地处理P_1,P_2即可.

如果直接暴力枚举两边的点，那么复杂度f(n)=2f(n/2)+O(n^2)=O(n^2\log n)，变差了，所以不可以这么做.

现在假设两个子集的答案已经求出，那么我们设d=min(solve(P_1),solve(P_2)),中位数的坐标是m，那么我们只需要处理所有坐标在[m-d,m+d]范围内的点即可。容易看出这样的点每边最多只有2个，否则他们它们之间的距离一定<d，矛盾，所以可以O(1)地处理，所以复杂度f(n)=2f(n/2)+O(1)=O(n)，考虑排序之后复杂度O(n\log n)

现在把坐标变成二维，上面的做法应该对我们有一些启发性.

先按照x坐标排序，然后找一个中位x坐标m，在这里画一条平行于y轴的分割线，把点分成P_1和P_2两个子集.设两个子集的答案的较小值是d，那么我们处理的点一定是x坐标在[m-d,m+d]范围内，也就是两个竖直长条.但这次我们没这么幸运，因为这两个长条内的点还是O(n)的.我们来暴力地尝试一下:

把这个区域内的点按y坐标排序，然后枚举每一个点，从它往后枚举第二个点，如果这两个点的y坐标之差>=d那么就停止枚举第二个点.

然后你发现你A掉了这道题.

为什么呢?因为满足上述条件的第二个点在两边各最多有6个。所以复杂度是可以保证的.为什么是6个呢?这里给出证明.

显然对于每一个点，到它的距离<d的点在每一边一定会落在一个d\times2d的矩形之内(其实是个半径为d的圆，但是圆难以处理，所以用矩形近似).这个矩形内的点需要满足两两之间的距离>=d.这样的点如果>6个，那么我们用鸽巢原理:把d\times 2d的矩形切成6个\dfrac{1}{2}d\times\dfrac{2}{3}d的小矩形，那么一定有两个或以上的点落在同一个小矩形内，但是这个小矩形中两点的最大距离等于对角线长，也就是\dfrac{5}{6}d<d，矛盾.因此最多只有六个点。

于是我们枚举每一个点，找这些点就可以了

到这里算法已经明确，但实现上出现了一些问题:

1. 如果你合并答案用stl的sort，那么复杂度f(n)=2f(n/2)+O(nlogn)=O(n\log^2n)就不对了.我们需要归并排序.这样我们就不可能只对两个长条内的点排序，而是需要对所有正在处理的区间内的点排序了.归并的复杂度也是基于递归的，并且处理子问题的时候两个序列已经有序，所以归并排序可以把总时间复杂度减小到O(n\log n).但是这道题数据水，所以sort可以取得更加优秀的效率.说一下怎么卡:所有的点全都在一条直线上，就可以把sort卡到极限.