hdu_1007_Quoit Design(最近点对)

题目连接：hdu_1007_Quoit Design

题意：

给你平面上的一些点，让你找出这些点的最近点对的距离

题解：
采用分治，达到O(nlognlogn)的时间复杂度就能艹过去了

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<math.h>

 using namespace std;

 //O(nlognlogn)找最近点对

 const int N=1e5+;

 struct TPoint

 {

     double x,y;

 }ply[N],ans[N];

 int n;

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

 bool cmpx(TPoint a,TPoint b) {return a.x<b.x;}

 bool cmpy(TPoint a,TPoint b) {return a.y<b.y;}

 double dist(TPoint a,TPoint b)

 {

     double s1=a.x-b.x;

     double t1=a.y-b.y;

     return sqrt(s1*s1+t1*t1);

 }

 double closest(int l,int r)

 {

     if(l+==r) return dist(ply[l],ply[r]);//2点

     else if(l+==r)//三点

         return MIN(dist(ply[l],ply[l+]),MIN(dist(ply[l],ply[r]),dist(ply[l+],ply[r])));

     int i,j,mid,cnt;

     mid=(l+r)>>;

     double mi=MIN(closest(l,mid),closest(mid+,r));//递归解决

     for(i=l,cnt=;i<=r;i++)//相邻点符合

     {

         if(fabs(ply[i].x-ply[mid].x)<=mi)

             ans[cnt++]=ply[i];

     }

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

     for(i=;i<cnt;i++)for(j=i+;j<cnt;j++)//更新最小距离

     {

         if(ans[j].y-ans[i].y>=mi) break;

         mi=MIN(mi,dist(ans[i],ans[j]));

     }

     return mi;

 }

 int main()

 {

     while(scanf("%d",&n),n)

     {

         int i;

         for(i=;i<n;i++) scanf("%lf%lf",&ply[i].x,&ply[i].y);//输入点

         sort(ply,ply+n,cmpx);//按x排序

         double mi=closest(,n-);

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

     }

     return ;

 }