杭电1000到1050 acm解题报告

//1007找出给定一堆点中最短两点距离 2656MS 7152K #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int N=1000000; const double eps=0.00001; //精度 typedef struct TYPE { double x,y; int index; } Point; //存每点的坐标和索引值 Point a[N],b[N],c[N]; inline double min(double p,double q) { return p>q?q:p; } double dis(Point p,Point q) { double x1=p.x-q.x,y1=p.y-q.y; return sqrt(x1*x1+y1*y1); } int merge(Point p[],Point q[],int s,int m,int t) //将数组q保存到p，且对y升序排序 { int i,j,k; for(i=s,j=m+1,k=s;i<=m&&j<=t;) { if(q[i].y>q[j].y) p[k++]=q[j++]; else p[k++]=q[i++]; } while(i<=m) p[k++]=q[i++]; while(j<=t) p[k++]=q[j++]; memcpy(q+s,p+s,(t-s+1)*sizeof(p[0])); return 0; } double closest(Point a[],Point b[],Point c[],int p,int q) {//核心函数 if(q-p==1) //递归的最终条件 return dis(a[p],a[q]);//只剩2点时 计算两点距离 else if(q-p==2)//只剩3点时 取最小的两点距离 { double x1=dis(a[p],a[q]); double x2=dis(a[p+1],a[q]); double x3=dis(a[p],a[p+1]); if(x1<x2&&x1<x3)//距离各不相同 return x1; else if(x2<x3)//两个距离相同 return x2; else //距离一样 return x3; }//递归过程中 int m=(p+q)/2; //中间点 int i,j,k; double d1,d2; for(i=p,j=p,k=m+1;i<=q;i++)//按照x方向平分左右点赋给c[] if(b[i].index<=m) c[j++]=b[i]; //数组左半部分保存划分的左部，对y升序的 else c[k++]=b[i]; //数组右半部分保存划分的右部，对y升序的 d1=closest(a,c,b,p,m);//递归 再对左右二分求最小 d2=closest(a,c,b,m+1,q); double dm=min(d1,d2); merge(b,c,p,m,q); //将数组c保存到b，且对y升序的 for(i=p,k=p;i<=q;i++) if(fabs(b[i].x-b[m].x)<dm) c[k++]=b[i]; //将离划分线b[m].x距离不超过dm的部分保存到数组c for(i=p;i<k;i++) for(j=i+1;j<k&&c[j].y-c[i].y<dm;j++) { double temp=dis(c[i],c[j]); if(temp<dm) dm=temp; } return dm; } int cmp_x(const void *p,const void *q) //按x升序排序 { double temp=((Point*)p)->x-((Point*)q)->x; if(temp>0) return 1; else if(fabs(temp)<eps)//fabs求双精度浮点数的绝对值 return 0; else return -1; } int cmp_y(const void *p,const void *q) //按y升序排序 { double temp=((Point*)p)->y-((Point*)q)->y; if(temp>0) return 1; else if(fabs(temp)<eps) return 0; else return -1; } int main() { int n,i; double d; while(scanf("%d",&n)!=EOF&&n) { for(i=0;i<n;i++) scanf("%lf %lf",&(a[i].x),&(a[i].y)); qsort(a,n,sizeof(a[0]),cmp_x); //对a按x升序排序 for(i=0;i<n;i++) a[i].index=i; memcpy(b,a,n*sizeof(a[0]));//由a所指内存区域复制count个字节到b所指内存区域 qsort(b,n,sizeof(b[0]),cmp_y); //对b按y升序排序 d=closest(a,b,c,0,n-1); //求最近点对的距离 printf("%.2lf\n",d/2); } return 0; }