怎样计算二维平面中最近的两个点
这是经典的分治例题“平面最近点对”，参考此链接http://m.blog.csdn.net/blog/lonelycatcher/7973046
■网友
典型的分治算法，
一般想到分治法，我们一般最开始可能就会想到，把n个点分成左右两部分， 为了将平面上的点集S分割为大小大致相同的2个子集S1和S2， 我们可以首先把所有点根据横坐标x从小到大排序，我们选取x=mid来作为分割线。其中，mid为S中所有点的横坐标的中位数。 这样可以将点集合S分为2部分，S1={P属于S| x(p)\u0026lt;=m} 和 S2={P属于S| x(p)\u0026gt;m}, 这样S1和S2中坐标点的个数大致相等。
然后分别求左、右两部分里面点的最短距离(设其最短距离分别为left_min和right_min)，现在设d=min(left_min,right_min),若S中存在最近点对（p,q）之间的距离小于d，那么p和q必分属于S1和S2,p,q的横坐标距直线x=mid的距离也均小于d.
【怎样计算二维平面中最近的两个点】 
在一维的情况下，距分割点距离为d的2个区间(mid-d,mid)和(mid,mid+d)中最多各有一个点(若多余一个点，与左右区间最小距离为d矛盾)。在二维情况下则要稍微复杂些， 最坏情况下可能左右各有n/2个点， 那么如果我们遍历这n/2个点对，需要的时间为n*n/4, 这样做时间效率太低，显然我们不能这样做。考虑到对P1中任意一点p，若他与p2中的某个点q构成一个最短距离，设p的坐标为(x,y),那么显然q的横坐标的范围为（mid,mid+d）,纵坐标范围为(y-d,y+d). 
那么对于每一个点p, 与其构成最短距离的点必然在一个d*2d的矩形框内（该矩形框内可能有多个点，但是任意2个点之间的距离都不超过d，接下来我们证明该矩形框中的点最多不超过一个常数），我们把该矩形框划分为d个(d/2)*(2d/3)的矩形， 由于该矩形的对角线长度为(d/2)2+(2d/3)2?????????????√=5d/6 小于d, 故每个矩形框内实际上最多只可能有一个这样的点， 这样对于任意一个点p，与其对应的可能构成最小距离的点最多不超过6个，这样左右之间的匹配次数最多是6n次。 我们可以把距离x=mid左右距离不超过d的所有的点按纵坐标排序，这样在找这些点时会方便一些。 这样时间复杂度T(n)=2T(n/2)+O(n), T(n)=O(n*logn) 。
更详细和代码，请参考链接：
平面最近点距离问题(分治法) - 博客频道 - CSDN.NET
■网友
随机增量算法可以做到O(n)。大概方法是若假设答案为ans，则可以把平面切成边长为ans的正方形网格，用hash表把所有点放入网格中，每次枚举一个点后，可以在周围9个网格里寻找离它最近的点。ans是动态更新的。
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 有啥方法，网站，项目可以自己练习计算广告学
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采