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

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

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

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

R e t u r n ; }

// n較大

將點(diǎn)集分成大致相等的兩個(gè)部分A和B

確定A和B中的最近點(diǎn)對(duì)

確定一點(diǎn)在A中、另一點(diǎn)在B中的最近點(diǎn)對(duì)

從上面得到的三對(duì)點(diǎn)中，找出距離最小的一對(duì)點(diǎn)

圖14-13 尋找最近的點(diǎn)對(duì)

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

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

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

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

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

1. 選擇數(shù)據(jù)結(jié)構(gòu)

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

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

程序14-8 點(diǎn)類

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; // 點(diǎn)的編號(hào)

float x, y; // 點(diǎn)坐標(biāo)

} ;

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中相同點(diǎn)的索引

float x, y; // 點(diǎn)坐標(biāo)

} ;

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

算法設(shè)計(jì)與分析
第二章——分治

#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;?
}?