HDU 1007 Quoit Design最近点对（ 分治法）

题意：

　　给出平面上的n个点，问任意点对之间的最短距离是多少？

思路：

　　先将所有点按照x坐标排序，用二分法将n个点一分为二个部分，递归下去直到剩下两或一个点。对于一个部分，左右部分的答案分别都知道，那么可能的答案就是min(left_ans,right_ans) 。注意更小的点对可能一个在左，一个在右。所以还得处理两个边内的紧靠着的部分，如果左边的一个点到达中线的距离已经超过当前最短距离，那么这个点到达右边任意一个点也不会是最短距离了。同时，若一左一右的两个点的y距离已经超过目前最短距离，那么也不可能是最短距离，可能为答案的点对并不太多，大概O(n)对。因此，还得在x距离满足的情况下，y也得满足，所以y也得排序。

 #include <bits/stdc++.h>

 using namespace std;

 struct node

 {

     double x,y;

 }a[];

 int c[];

 double cmpy(int t1,int t2) { return a[t1].y<a[t2].y;}

 bool cmp(node t1,node t2) { return t1.x<t2.x; }

 double dis(node t1,node t2) {return sqrt((t1.x-t2.x)*(t1.x-t2.x)+(t1.y-t2.y)*(t1.y-t2.y));}

 double find(int left,int right)

 {

     if(left+==right)    return dis(a[left],a[right]);

     if(left==right)        return 2147483.999;

     int mid=(left+right)>>;

     double aa=find(left,mid);

     double bb=find(mid+,right);

     double ans=min(aa,bb); //当前最小

     int cnt=;

     double x=a[mid].x;

     for(int i=left; i<=right; i++)

         if(fabs(a[i].x-x)<ans)    c[cnt++]=i;

     sort(c,c+cnt,cmpy);        //按y来排序

     for(int i=;i<cnt;i++)        //计算x=[mid-ans，mid+ans]

         for(int j=i+;j<cnt;j++)

         {

             if(a[c[j]].y-a[c[i]].y>ans)    break; //两点的距离已超过ans

             ans=min(ans,dis(a[c[i]],a[c[j]]));    //求最小距离

         }

     return ans;

 }

 int main()

 {

     int n,i;

     while(cin>>n,n)

     {

         for(i=;i<n;i++)

             scanf("%lf%lf",&a[i].x,&a[i].y);

         sort(a,a+n,cmp);      //按X排序

         printf("%.2lf\n",find(,n-)/);

     }

     return ;

 }

AC代码