求平面上某个点集的最近与最远距离

最近距离

分治思想：将这个点集进行分割，两边的数目大致相等，称作left和right，假设求出了left和right中的最近距离为ML,MR，则该点集的最近距离为ML、MR、left中的点与right中的最短距离这三个值中的最小值。设MD=min(ML,MR)

而在求left与right中的点的距离最小值时，可以通过简化计算，在分割线左右MD范围内的，按照y坐标进行排序，只要求该点上下MD范围内的最多8个点的距离即可。如下所示： MDLR

MDLR

MDMD

因此可以再O(N)的时间复杂度之内求出left与right中的点的最短距离，在于MD尽心比较即可得出答案。

最远距离

先求该点集的凸包（即包含所有点的凸多边形）（Graham扫描算法）

然后求该凸包的直径（旋转卡壳算法）

可参考文献：

旋转卡壳算法：http://www.cppblog.com/staryjy/archive/2009/11/19/101412.html

http://blog.csdn.net/wangyangkobe/article/details/6081975