今天看编程之美,看到求平面中两点的最近距离,书中给出了O(nlogn)算法,主要是采用分治的方法来做的,首先将平面的点按x坐标分为两部分,分别求最近点对,然后是合并;合并过程中对于两个点分别在两个区域的分析非常巧妙,有效地减少了需要比较的点对的个数。

在poj中对应的题目3714

然后又看到了扩展问题:如何求平面中最远的两个点的距离

这个就不能继续套用“最近距离点对”的分治策略,上网查了下,原来是使用凸包算法+旋转卡壳算法,poj中对应的题目是2187和3608

这里简单记录下,明天做下这两个题目

关于凸包算法和旋转卡壳算法的介绍:

http://yishan.cc/blogs/gpww/archive/2011/02/16/graham-s-scan.aspx

http://www.cppblog.com/staryjy/archive/2010/09/25/101412.html

http://yishan.cc/blogs/gpww/archive/2011/02/15/1787.aspx

ax操作的时间复杂度为