给定点集A和点集B，两个点集分别有N个顶点。
问任意顶点对(a,b)的最近距离是多少，其中a属于A，b属于B。
输入 第一行为数据个数T，表示接下来有T个测试数据。 对于每个测试数据： 第一行为顶点个数N。（N<=100,000） 接下来N行，每行两个整数，表示点集A中的N个点的坐标。 再接下来N行，每行两个整数，表示点集B中的N个点的坐标。 其中坐标均为小于等于1000000000的非负整数。 输出 对于每组测试数据，输出最近点对(a,b)的距离，其中a属于A，b属于B。保留3位小数。 样例输入 2 4 0 0 0 1 1 0 1 1 2 2 2 3 3 2 3 3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 样例输出 1.414 0.000 来源 poj3714 #include<iostream> #include<iomanip> #include<cmath> #include<cstring> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> #include<stack> #include<list> using namespace std; struct Point { double x,y; bool flag; }p[200005]; int tep[200005]; double dis(const Point &a,const Point &b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double Min; bool cmpx(const Point &a,const Point &b) { return (a.x<b.x||a.x==b.x&&a.y<b.y); } bool cmpy(const int &a,const int &b) { return (p[a].y<p[b].y||p[a].y==p[b].y&&p[a].x<p[b].x); } double Merge(int s,int e) { double ans=1e100,ans1; if(s==e) { return ans; } if(s==e-1) { if(p[s].flag!=p[e].flag) { ans=dis(p[s],p[e]); return ans; } } int mid=(s+e)/2; ans=Merge(s,mid); ans1=Merge(mid+1,e); if(ans>ans1)ans=ans1; int cnt=0; for(int i=s;i<=e;++i) { if(fabs(p[i].x-p[mid].x)<ans) { tep[cnt]=i; cnt++; } } sort(tep,tep+cnt,cmpy); for(int i=0;i<cnt;++i) { for(int j=i+1;j<cnt;++j) { if(fabs(p[tep[i]].y-p[tep[j]].y)>=ans) { break; } double t=dis(p[tep[i]],p[tep[j]]); if(p[tep[i]].flag!=p[tep[j]].flag&&t<ans) { ans=t; } } } return ans; } int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;++i) { scanf("%lf%lf",&p[i].x,&p[i].y); p[i].flag=0; } for(int i=n;i<(n<<1);++i) { scanf("%lf%lf",&p[i].x,&p[i].y); p[i].flag=1; } sort(p,p+(n<<1),cmpx); Min=Merge(0,(n<<1)-1); printf("%.3lf\n",Min); } return 0; }