HDU 1007 Quoit Design（分治）

Description   给出n个点的坐标，输出点集中距离最近两点间距离的一半  Input   多组输入，每组用例第一行为点数n，之后n行每行两个浮点数表示一个点的横纵坐标，以n=0结束输入  Output   对于每组用例，输出点集中距离最近的两点间距离的一半  Sample Input   2  0 0  1 1  2  1 1  1 1  3  -1.5 0  0 0  0 1.5  0  Sample Output   0.71  0.00  0.75  Solution   这个题目其实就是求最近点对的距离，暴力显然不行，所以要用分治。  先把n个点按x坐标排序，然后求左边n/2个和右边n/2个的最近距离，最后合并，主要说说合并：  首先，假设点是n个，编号为1到n，找一个中间的编号mid，先求出1到mid所有点的最近距离设为d1，还有mid+1到n所有点的最近距离设为d2。这里的点需要按x坐标的顺序排好，并且假设这些点中，没有2点在同一个位置（若有，最小距离为0）。  然后，令d=min(d1,d2)，如果说最近点对中的两点都在1-mid集合或者mid+1到n集合中，则d就是最小距离了，但是还有可能的是最近点对中的两点分属这两个集合，所以我们必须检测一下这种情况是否会存在，若存在，则把这个最近点对的距离记录下来去更新d，这样我们就可以得道最小的距离d了。 

关键是检测最近点对，理论上每个点都要和对面集合的点匹配一次，但那样的效率还是不能满足要求，所以这里要优化：以我们所选的分割点mid为界，如果某一点的横坐标到点mid的横坐标的绝对值超过d1并且超过d2，那么这个点到mid点的距离必然超过d1和d2中的小者，所以这个点到对方集合的任意点的距离必然不是所有点中最小的。所以我们先把在mid为界左右一个范围内的点全部筛选出来，放到一个集合里。筛选好以后如果把这些点两两求距离去更新d还是很慢，还得继续优化：首先把这些点按y坐标排序，假设排序好以后有cnt个点，编号为0到cnt-1。那么我们用0号去和从1号到cnt-1号的点求一下距离，然后1号和从2到cnt-1号的点求一下距离，用求出的距离不断更新d，如果某两个点的y轴距离已经超过了d就可以直接退出循环开始从下一个点查找了 

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f #define maxn 100010 struct node { double x,y; }; node p[maxn],t[maxn]; int cmpxy(node a,node b)//将点按横坐标升序排,横坐标相同按纵坐标升序排 { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int cmpy(node a,node b)//将点按纵坐标升序排 { return a.y<b.y; } double dis(node a,node b)//求两点间距离 { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double closest(int left,int right)//分治求下标从left到right的点集中两点间最短距离 { double d=INF;//初始化最短距离 if(left==right)//集合中只有一个点时返回d值 return d; if(left+1==right)//集合中只有两个点的时候返回这两点间距离 return dis(p[left],p[right]); int mid=(left+right)/2;//分治 double d1=closest(left,mid); double d2=closest(mid+1,right); d=min(d1,d2); int k=0; for(int i=left;i<=right;i++)//将mid附近一个可能出现最短距离的范围中的点拿出来另作讨论 if(fabs(p[i].x-p[mid].x)<=d) t[k++]=p[i]; sort(t,t+k,cmpy);//将这些点按纵坐标升序排 for(int i=0;i<k;i++)//枚举这些点间的距离来更新d for(int j=i+1;j<k&&t[j].y-t[i].y<d;j++)//当两点间纵坐标距离已经超过d则可以直接进入下一次循环 d=min(d,dis(t[i],t[j])); return d; } int main() { int n; while(scanf("%d",&n)==1&&n) { for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p,p+n,cmpxy);//将所有点排序 printf("%.2lf\n",closest(0,n-1)/2);//输出的是最短距离的一半 } return 0; }