关键是检测最近点对,理论上每个点都要和对面集合的点匹配一次,但那样的效率还是不能满足要求,所以这里要优化:以我们所选的分割点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; }