今天看编程之美，看到求平面中两点的最近距离，书中给出了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

最多留言日志

• 
• 
• 
• 
•