本文主要是介绍《DSAA》 10.2.2 最近点问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
设平面上有N个点，要找出其中两个相距最近的点，被称为最近点问题。如果简单地用蛮力解决：N个点存在N × (N - 1) / 2 条边，我们可以检查所有的边找出其中最短者，但是这样的时间界是O(N ^ 2)，比较浪费时间，还应该有更巧妙的办法，比如分治算法。
我们在平面中间画一条竖线，则点集p也被分成两半pL和pR，那么最近的一对点将会：
1）都在pL中，设其距离为dL
2）都在pR中，设其距离为dR
3）一个在pL中，另一个字pR中，设其距离为dC
dL和dR可以递归地求得，问题是如何得到dC，令dT = min(dL, dR)，我们在中心线的两侧距中心线dT的画两条竖线，只有当左右两个点都落在两条竖线之间的区域时，它们的距离才有可能小于dT，这样我们就大大缩小了点集的范围，可以用蛮力搞定了。
实现的时候为了方便，我用点集中的中间点的x坐标代替了中间线（希望不会有问题，呵呵）：
1）把点集存入一个数组，并按照x坐标排序
2）用分治算法递归求dL和dR，直到本区域只剩下：一个点，返回一个最大值，或两个点，返回其距离
3）令dT = min(dL, dR)， 挑出x坐标距中间点小于dT的点，用蛮力求出dC，最后返回min(dT, dC)
下面是对原书中示例的求解，运行结果如下：
这篇关于《DSAA》 10.2.2 最近点问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
