hdu1007平面最近点对分治

题目大意：给你N对点，求这N对点中两队点的距离的一半，精确到小数点后两位

暴力显然O（n^2)，不能过。

分治即可，对N对点对，求中间值，mid。按照横坐标升序排列，递归求出0到mid以及mid+1到N-1对点的最小距离。

分治关键步骤在合并。

我们求出两个最小距离，但是没有考虑一个点在左边，一个点在右边的情况。

 先求出两个最小距离中较小的一个，记为mdis

  根据mid点为分界点【mid-mdis,mid+mdis】的闭区间筛选出可能取得最小距离的点，因为平面上的点还包含纵坐标，所以水平

距离不在这个范围内不可能是最短距离。同理再对进入暂时数组（记为temp）的点对按纵坐标分类,再次筛选，并不断更新mdis

的值。

 #include <iostream> #include <cmath> #include <algorithm> using namespace std; struct Point{ double x,y; }; Point temp[100005];  Point point[100005];  bool cmpx(Point a,Point b) {     return a.x<b.x;  } bool cmpy(Point c,Point d) { return c.y<d.y;  } double dist(int t1,int t2) { return (pow((point[t1].x-point[t2].x),2)+pow((point[t1].y-point[t2].y),2));  }  double dis(int t1,int t2) { return (pow((temp[t1].x-temp[t2].x),2)+pow((temp[t1].y-temp[t2].y),2));  }  double dfs(int l,int r) { if(l+1==r)  return dist(l,r); if(l+2==r) return min(dist(l,r),min(dist(l,l+1),dist(l+1,r))); int mid=(l+r)>>1;  double leftmindis=dfs(l,mid);  double rightmindis=dfs(mid+1,r); double mdis=min(leftmindis,rightmindis); int tot=0; for(int i=l;i<=r;i++)     if(point[i].x<=point[mid].x+mdis&&point[i].x>=point[mid].x-mdis)      temp[tot++]=point[i];      sort(temp,temp+tot,cmpy);    for(int i=0;i<tot;i++)        for(int j=i+1;j<tot;j++)           if(temp[j].y-temp[i].y>=mdis) break;           else mdis=min(dis(i,j),mdis); return mdis; } int main() { int N; while(cin>>N&&N)  { for(int i=0;i<N;i++)   { scanf("%lf%lf",&point[i].x,&point[i].y);   }   sort(point,point+N,cmpx);   double ans=sqrt(dfs(0,N-1))/2;    printf("%.2lf\n",ans); } return 0; }