首页 > 代码库 > Quoit Design(hdu 1007)

Quoit Design(hdu 1007)

题意:给n个点的坐标,求距离最近的一对点之间距离的一半。第一行是一个数n表示有n个点,接下来n行是n个点的x坐标和y坐标。实数。 

/*
  最小点距离问题 
  采用分治算法,假设对于1-n的区间,我们已经求出1~m(m是中点)和m+1~n的结果分别是d1和d2。
  那么如果1~n的答案出现在这两个单独的区间内,很明显就是min(d1,d2),否则在两个区间之间产生。
  如果直接两重循环枚举两个区间的数会T,所以考虑优化:
  ①:如果某个点到m的距离大于min(d1,d2),那么不考虑。
  ②:首先用到一个结论:
        假设有一个点q,坐标是xq, yq。可以证明在以q为底边中点,长为2d,宽为d的矩形区域内不会有超过6个点
        (证明见算法导论,然而我并没看懂,Orz)
      有了这个结论之后,我们将第一次优化后的点按照y排序,对于一个点i,如果某个点j与i的y坐标之差大于之前求出的ans,那么j之后的就不用计算了。
(不是很明白复杂度的证明)
*/ #include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #define N 1000010 using namespace std; int n; struct node{ double x,y; };node qx[N],qy[N]; bool cmpx(const node&s1,const node&s2){ return s1.x<s2.x; } bool cmpy(const node&s1,const node&s2){ return s1.y<s2.y; } double getdis(node i,node j){ return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y)); } double solve(int s,int e){ if(s+1==e) return getdis(qx[s],qx[e]); if(s+2==e) return min(min(getdis(qx[s],qx[s+1]),getdis(qx[s+1],qx[e])),getdis(qx[s],qx[e])); int mid=s+e>>1,cnt=0; double ans=min(solve(s,mid),solve(mid+1,e)); for(int i=s;i<=e;i++) if(fabs(qx[i].x-qx[mid].x)<=ans) qy[++cnt]=qx[i]; sort(qy+1,qy+cnt+1,cmpy); for(int i=1;i<=cnt;i++){ for(int j=i+1;j<=cnt;j++){ if(qy[j].y-qy[i].y>=ans) break; ans=min(ans,getdis(qy[i],qy[j])); } } return ans; } void work(){ for(int i=1;i<=n;i++) scanf("%lf%lf",&qx[i].x,&qx[i].y); sort(qx+1,qx+n+1,cmpx); printf("%.2lf\n",solve(1,n)/2); } int main(){ while(1){ scanf("%d",&n); if(!n) break; work(); } return 0; }

 

Quoit Design(hdu 1007)