求平面最近點(diǎn)對(duì)的核心思想乃是二分，用遞歸實(shí)現(xiàn)。具體操作如下：

     若點(diǎn)的個(gè)數(shù)很少（比如小于3或者小于5），就直接枚舉。

     如點(diǎn)的個(gè)數(shù)很多，按現(xiàn)將所有點(diǎn)按X排序，并按X坐標(biāo)平均的分成左右兩個(gè)部分（假設(shè)分割線為X=nx），分別求出兩邊的最短距離minl與minr并令ans=min（minl，minr）。

     求出左右兩邊的最小值之后，剩下的工作就是合并。易見若該點(diǎn)集存在點(diǎn)對(duì)（a，b）的最近距離小于ans，則a，b一定分別在x=nx的兩邊，切nx-a.x與nx-b.x的絕對(duì)值肯定小于ans。

     據(jù)此我們可以將點(diǎn)集中所有X值在（nx-ans，nx+ans）的點(diǎn)都選出來，那么滿足條件的（a，b）肯定都在其中。

     易見若存在（a，b）兩點(diǎn)他們之間的距離小于ans，那么a.y-b.y的絕對(duì)值也肯定小于ans。

     綜上存在（a，b）兩點(diǎn)他們之間的距離小于ans那，（a，b）一定在一個(gè)長為2*ans寬為ans的矩形之中。而 且這個(gè)矩形被X=nx平分成兩個(gè)ans*ans的矩形，由于無論是在左邊還是在右邊，任意兩點(diǎn)的之間的距離總是小于等于ans的，所以兩個(gè)ans*ans 的矩形中最多只有4個(gè)點(diǎn)（分別在四個(gè)頂點(diǎn)上），長為2*ans寬為ans的矩形最多有8個(gè)點(diǎn)。

     據(jù)此我們將所有X值在（nx-ans，nx+ans）的點(diǎn)按他們的Y值進(jìn)行排序。依次看每個(gè)點(diǎn)與它之后的7個(gè)點(diǎn)的距離是否小于ans，若小于則更新ans，最后求出來的結(jié)果就是平面最近點(diǎn)對(duì)的距離。保留產(chǎn)生該距離的兩個(gè)點(diǎn)即可得到最近點(diǎn)對(duì)。

     練手題目：Pku2107，Vijos1012

附C++代碼（Pku2107）：

#include <iostream>
#include <cmath>

const long maxsize = 100000;

typedef struct 
{ 
double x, y; 
} PointType;

long list[maxsize], listlen,n;
PointType point[maxsize];

int sortcmp(const void *,const void *); 
double dis(PointType,PointType);
double getmin(double,double);
int listcmp(const void *,const void *); 
double shortest(long,long);
int init(void);

int main() 
{ 
while (init())
   printf("%.2lf\n",shortest(0, n - 1)/2);    
return 0;
}

int sortcmp(const void *a, const void *b) 
{ 
if (((PointType*)a)->x < ((PointType*)b)->x)    
   return -1;   
else 
   return 1; 
}

double dis(PointType a, PointType b) 
{ 
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); 
}

double getmin(double a, double b) 
{ 
return a<b?a:b;
}

int listcmp(const void *a, const void *b) 
{ 
if (point[*(int*)a].y < point[*(int*)b].y)    
   return -1;   
else 
   return 1; 
}

double shortest(long l, long r) 
{ 
if (r - l == 1) 
   return dis(point[l], point[r]);   
if (r - l == 2)    
   return getmin(getmin(dis(point[l], point[l+1]), dis(point[l], point[r])), dis(point[l+1], point[r]));   
long i, j, mid = (l + r) >> 1;   
double curmin = getmin(shortest(l, mid), shortest(mid + 1, r));   
listlen = 0;   
for (i = mid; i >= l && point[mid+1].x - point[i].x <= curmin; i --)    
   list[listlen++] = i;   
for (i = mid + 1; i <= r && point[i].x - point[mid].x <= curmin; i ++)    
   list[listlen++] = i;   
qsort(list, listlen, sizeof(list[0]), listcmp);   
for (i = 0; i < listlen; i ++)    
   for (j = i + 1; j < listlen && point[list[j]].y - point[list[i]].y <= curmin; j ++)     
    curmin = getmin(curmin, dis(point[list[i]], point[list[j]]));   
return curmin; 
}

int init(void)
{
int i;
scanf("%d", &n);      
for (i=0;i<n;i++) 
   scanf("%lf%lf",&point[i].x,&point[i].y);      
qsort(point,n,sizeof(point[0]),sortcmp);
return n;
}


自己寫的代碼: