watchpoints
commented
5 years ago 用45分钟 没想出来
看别人答案 第三点合并部分没看懂.依然没看懂
思路：把点集分为两半，最近点对可能全部属于左半点集，或者右半点集，或者一个属于左半点集，一个属于右半点集。所以最终结果为这三种情况的最小值。
分治法一般分为三个步骤：
1 分解：将 n 个点按照横坐标排序，并按照 1~n编号， 分成两部分：1~⌊n2⌋、⌈n2⌉~n。
2 解决：分别求出左右两部分中的最近点对距离，记为 d1 和 d2d，取 d=min(d1,d2))。
时间复杂度为 2T(n2) （这里通常采用递归的办法）
3 合并：这一步考虑的问题是，最近点对可能分别来自左半部分点集和右半部分点集， 所以如果存在这样一个最近点对距离比 d 还小， 那么返回该值，否则返回 d。 ————————————————
给定平面上的N个点，寻找距离最远/最近的两个点