【每日一题】- 2019-09-27 - 寻找距离最远/最近的两个点

[watchpoints]

给定平面上的N个点，寻找距离最远/最近的两个点

[watchpoints]

用45分钟 没想出来

看别人答案 第三点合并部分没看懂.依然没看懂

思路：把点集分为两半，最近点对可能全部属于左半点集，或者右半点集，或者一个属于左半点集，一个属于右半点集。所以最终结果为这三种情况的最小值。

分治法一般分为三个步骤：

1 分解：将 n 个点按照横坐标排序，并按照 1~n 编号， 分成两部分：1~⌊n2⌋、⌈n2⌉~n。
2 解决：分别求出左右两部分中的最近点对距离，记为 d1 和 d2d，取 d=min(d1,d2))。

时间复杂度为 2T(n2) （这里通常采用递归的办法）

3 合并：这一步考虑的问题是，最近点对可能分别来自左半部分点集和右半部分点集，
所以如果存在这样一个最近点对距离比 d 还小，
那么返回该值，否则返回 d。
————————————————