HDU 1007 Quoit Design(分治)

    xiaoxiao2021-03-25  98

    Description   给出n个点的坐标,输出点集中距离最近两点间距离的一半  Input   多组输入,每组用例第一行为点数n,之后n行每行两个浮点数表示一个点的横纵坐标,以n=0结束输入  Output   对于每组用例,输出点集中距离最近的两点间距离的一半  Sample Input   0 0  1 1  1 1  1 1  -1.5 0  0 0  0 1.5  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; }

    转载请注明原文地址: https://ju.6miu.com/read-14500.html

    最新回复(0)