屈婉玲专题
平面内有n个点，如何快速求出距离最近的点对？【分治法】【屈婉玲教材】
题目如标题，很容易想到劈成两半，每一半各求最近的，最后merge 难点在f(n)如何估计，假设两个子问题的点集分别是left和right，两部分的最近距离分别是d1和d2，所以有可能的最小距离δ=min(d1,d2)。如果left中的每一个点都要和right中的每一个点求距离，那么f(n)=n^2，分治算法是不会简化的。幸运的是如果left中的每一个点最多只需要和right中的最多6个点比较