uva 10245 - The Closest Pair Problem

<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1186">点击打开链接uva 10245</a>

题目意思：  

给定N个点，找到所有点中距离最小的

解题思路：

1：递归+分治

《网上大牛的解释如下》

2在二维空间里，可用分治法求解最近点对问题。预处理：分别根据点的x轴和y轴坐标进行排序，得到X和Y,很显然此时X和Y中的点就是S中的点。

           1情况（1）：点数小于等于三时：                      

           2情况（2）：点数大于三时：

           3首先划分集合S为SL和SR，使得SL中的每一个点位于SR中每一个点的左边，并且SL和SR中点数相同。分别在SL和SR中解决最近点对问题，得到DL和DR，分别表示SL和SR中的最近点对的距离。令d=min(DL,DR)。如果S中的最近点对(P1,P2)。P1、P2两点一个在SL和一个在SR中，那么P1和P2一定在以L为中心的间隙内，以L-d和L+d为界

           4如果在SL中的点P和在SR中的点Q成为最近点对，那么P和Q的距离必定小于d。因此对间隙中的每一个点，在合并步骤中，只需要检验yp+d和yp-d内的点即可。

3《解题步骤》

步骤1：根据点的y值和x值对S中的点排序。

步骤2：找出中线L将S划分为SL和SR

步骤3：将步骤2递归的应用解决SL和SR的最近点对问题，并令d=min(dL,dR)。

步骤4：将L-d~L+d内的点以y值排序，对于每一个点(x1,y1)找出y值在y1-d~y1+d内的所有点，计算距离为d'。如果d'小于d，令d=d'，最后的d值就是答案

代码：