給定n 個點（xi，yi）（1≤i≤n），要求找出其中距離最近的兩個點。

例14-7 假設在一片金屬上鉆n 個大小一樣的洞，如果洞太近，金屬可能會斷。若知道任意兩個洞的最小距離，可估計金屬斷裂的概率。這種最小距離問題實際上也就是距離最近的點對問題。

通過檢查所有的n(n- 1 ) / 2對點，并計算每一對點的距離，可以找出距離最近的一對點。這種方法所需要的時間為(n2 )。我們稱這種方法為直接方法。圖1 4 - 1 3中給出了分而治之求解算法的偽代碼。該算法對于小的問題采用直接方法求解，而對于大的問題則首先把它劃分為兩個較小的問題，其中一個問題（稱為A）的大小為「n /2ù，另一個問題（稱為B）的大小為「n /2ù。初始時，最近的點對可能屬于如下三種情形之一： 1) 兩點都在A中（即最近的點對落在A中）；2) 兩點都在B中；3) 一點在A，一點在B。假定根據(jù)這三種情況來確定最近點對，則最近點對是所有三種情況中距離最小的一對點。在第一種情況下可對A進行遞歸求解，而在第二種情況下可對B進行遞歸求解。

if (n較小) {用直接法尋找最近點對

R e t u r n ; }

// n較大

將點集分成大致相等的兩個部分A和B

確定A和B中的最近點對

確定一點在A中、另一點在B中的最近點對

從上面得到的三對點中，找出距離最小的一對點

圖14-13 尋找最近的點對

為了確定第三種情況下的最近點對，需要采用一種不同的方法。這種方法取決于點集是如何被劃分成A、B的。一個合理的劃分方法是從xi（中間值）處劃一條垂線，線左邊的點屬于A，線右邊的點屬于B。位于垂線上的點可在A和B之間分配，以便滿足A、B的大小。

例2-8 考察圖14-14a 中從a到n的1 4個點。這些點標繪在圖14-14b 中。中點xi = 1，垂線x = 1如圖14-14b 中的虛線所示。虛線左邊的點(如b, c, h, n, i)屬于A，右邊的點(如a, e, f, j, k, l) 屬于B。d, g, m 落在垂線上，可將其中兩個加入A, 另一個加入B，以便A、B中包含相同的點數(shù)。假設d ,m加入A，g加入B。

設是i 的最近點對和B的最近點對中距離較小的一對點。若第三種情況下的最近點對比小。則每一個點距垂線的距離必小于，這樣，就可以淘汰那些距垂線距離≥ 的點。圖1 4 - 1 5中的虛線是分割線。陰影部分以分割線為中線，寬為2 。邊界線及其以外的點均被淘汰掉，只有陰影中的點被保留下來，以便確定是否存在第三類點對（對應于第三種情況）其距離小于。用RA、RB 分別表示A和B中剩下的點。如果存在點對(p,q)，p?A, q?B且p, q 的距離小于，則p?RA，q?RB。可以通過每次檢查RA 中一個點來尋找這樣的點對。假設考察RA 中的p 點，p的y 坐標為p.y，那么只需檢查RB 中滿足p.y- ＜q.y＜p.y+ 的q 點，看是否存在與p 間距小于的點。在圖14-16a 中給出了包含這種q 點的RB 的范圍。因此，只需將RB 中位于×2 陰影內的點逐個與p 配對，以判斷p 是否是距離小于的第三類點。這個×2 區(qū)域被稱為是p 的比較區(qū)（comparing region）。

例2-9 考察例2 - 8中的1 4個點。A中的最近點對為(b,h)，其距離約為0 . 3 1 6。B中最近點對為(f, j)，其距離為0 . 3，因此= 0 . 3。當考察是否存在第三類點時，除d, g, i, l, m 以外的點均被淘汰，因為它們距分割線x= 1的距離≥ 。RA ={d, i, m}，RB= {g, l}，由于d 和m 的比較區(qū)中沒有點，只需考察i即可。i 的比較區(qū)中僅含點l。計算i 和l的距離，發(fā)現(xiàn)它小于，因此(i, l) 是最近的點對。

為了確定一個距離更小的第三類點，RA 中的每個點最多只需和RB 中的6個點比較，如圖1 4 - 1 6所示。

1. 選擇數(shù)據(jù)結構

為了實現(xiàn)圖1 4 - 1 3的分而治之算法，需要確定什么是“小問題”以及如何表示點。由于集合中少于兩點時不存在最近點對，因此必須保證分解過程不會產生少于兩點的點集。如果將少于四點的點集做為“小問題”，就可以避免產生少于兩點的點集。

每個點可有三個參數(shù)：標號， x 坐標，y 坐標。假設標號為整數(shù)，每個點可用P o i n t l類（見程序1 4 - 8）來表示。為了便于按x 坐標對各個點排序，可重載操作符＜=。歸并排序程序如1 4 -3所示。

程序14-8 點類

class Point1 {

friend float dist(const Point1&, const Point1&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&,float&);

friend void main();

p u b l i c :

int operator<=(Point1 a) const

{return (x <= a.x);}

p r i v a t e :

int ID; // 點的編號

float x, y; // 點坐標

} ;

class Point2 {

friend float dist(const Point2&, const Point2&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&, float&);

friend void main();

p u b l i c :

int operator<=(Point2 a) const

{return (y <= a.y);}

p r i v a t e :

int p; // 數(shù)組X中相同點的索引

float x, y; // 點坐標

} ;

所輸入的n 個點可以用數(shù)組X來表示。假設X中的點已按照x 坐標排序，在分割過程中如果當前考察的點是X [l :r]，那么首先計算m= (l+r) / 2，X[ l:m]中的點屬于A，剩下的點屬于B。計算出A和B中的最近點對之后，還需要計算RA 和RB，然后確定是否存在更近的點對，其中一點屬于RA，另一點屬于RB。如果點已按y 坐標排序，那么可以用一種很簡單的方式來測試圖1 4 - 1 6。按y 坐標排序的點保存在另一個使用類P o i n t 2 (見程序14-8) 的數(shù)組中。注意到在P o i n t 2類中，為了便于y 坐標排序，已重載了操作符＜＝。成員p 用于指向X中的對應點。

算法設計與分析
第二章——分治

#include? < algorithm > ?
#include? < iostream > ?
#include? < cmath > ?
using?namespace?std;?
#define?abst(a,b)?(a>b?(a-b):(b-a))?
typedef?double?TYPE;?
#define?Abs(x)?((x)>0???(x)?:?-(x))?
#define?Sgn(x)?((x) < 0? ??(-1)?:?(1))?
#define?Max(a,b)?((a) > (b)???(a)?:?(b))?
#define?Min(a,b)?((a) < (b )???(a)?:?(b))?
#define?Epsilon?1e-8?
#define?Infinity?1e10?
const?double?PI =acos(-1.0);?

struct?MPOINT?{?
????MPOINT(int?xx =0,int? yy =0,int? tt =0):x(xx),y(yy),type(tt){}?
???? int?x;?
????int?y;?
????int?type;?
};?
MPOINT?point[1000010];?
double?result;?
bool?cmp(MPOINT?s,MPOINT?t)?
{?
????return?s.x<t.x;?
}?
double?len(MPOINT&?a,MPOINT&?b)?
{?
????return?sqrt(double(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y)));?
}?
double?mergepoint(int?l,int?r)?
{?
????double?resultl =0,resultr=0,minlen=1000000000;?
???? if(r > l+4)?{?
????????int?mid=(l+r)>>1;?
????????double?tempdis;?
????????resultl=mergepoint(l,mid);?
????????resultr=mergepoint(mid,r);?
????????minlen=min(resultl,resultr);?
????????for(int?i=mid;i>=l& &point [i].x>point[mid].x-minlen;i--)?{?
????????????for(int?j=mid;j < =r &&point[j].x<point[mid].x+minlen;j++)?{?
????????????????if(point[i].type! =point[j].type&&abst(point[j].y,point[mid].y)<minlen)? {?
????????????????????tempdis =len(point[i],point[j]);?
???????????????????? if(tempdis<minlen)?{?
????????????????????????minlen =tempdis;?
???????????????????? }?
????????????????}?
????????????}?
????????}?
????}?
????else?
????{?
????????double?distemp;?
????????for(int?i =l;i<r;i++)? {?
????????????for(int?j =l+1;j<=r;j++)? {?
????????????????if(j ==i)? {?
????????????????????continue;?
????????????????}?
????????????????if(point[i].type! =point[j].type)? {?
????????????????????distemp =len(point[i],point[j]);?
???????????????????? minlen =minlen>distemp?distemp:minlen;?
???????????????? }?
????????????}?
????????}?
????}?
????return?minlen;?
}?
int?input()?
{?
????int?n;?
????scanf("%d",&n);?
????????for(int?i =0;i<n;i++)? {?
????????????scanf("%d%d",&point[i].x,&point[i].y);?
????????????point[i].type =0;?
???????? }?
????????for(int?i =n;i<(n<<1);i++)? {?
????????????scanf("%d%d",&point[i].x,&point[i].y);?
????????????point[i].type =1;?
???????? }?
????????return?n;?
}?
int?main()?
{?
????int?cas,n,x,y;?
????scanf("%d",&cas);?
????while(cas--)?{?
????????result =0;?
???????? n =input();?
???????? sort(&point[0],&point[n<<1],cmp);?
????????double?result =mergepoint(0,(n<<1)-1);?
???????? printf("%.3lf\n",result);?
????}?
????return?1;?
}?