最近点对问题是一个经典问题，目标是在n个点中找到距离最近的一对点。做法可以有很多，直接上KD-Tree都是可以的。但最常用的还是分治法。其主要思想很简单，就是把问题分成两个子问题，再进行合并。不过在这之前，我们要先对点按x排序。求解时先把一堆点平均分成两堆点，分别递归求解两堆点的最近点对，记为和，然后取。之后我们把横坐标距离中间点在范围之内的点取出来，找它们之间的最近点对，与取即可。不过这里面有个...

阅读全文 »