C++

C++

1. 问题描述、

问题描述：最接近点对问题，给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。

1. 设计思路

设计思路：设S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px>m}。从而使S1和S2分别位于直线l的左侧和右侧，且S=S1∪S2。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离d1和d2。现设d=min(d1,d2)。若S的最接近点对(p,q)之间的距离d(p,q)<d则p和q必分属于S1和S2。不妨设p∈S1，q∈S2。那么p和q距直线l的距离均小于d。因此，我们若用P1和P2分别表示直线l的左边和右边的宽为d的2个垂直长条，则p∈S1，q∈S2，如图所示:

   距直线l的距离小于d的所有点

     在一维的情形，距分割点距离为d的2个区间(m-d,m](m,m+d]中最多各有S中一个点。因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些，此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这n^2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者，则必有d(p,q)<d。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个d×2d的矩形R中，如下图所示: