POJ3714：求平面最近点对
寻找两个集合中的点的最近点对
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 const double oo=1e50; 7 int n; 8 double ab(double x) 9 { 10 return x>0?x:-x; 11 } 12 struct node 13 { 14 double x,y; 15 bool bel; 16 }a[200010],temp[200010]; 17 bool cx(const node &a,const node &b) 18 { 19 return a.x<b.x; 20 } 21 bool cy(const node &a,const node &b) 22 { 23 return a.y<b.y; 24 } 25 double min(double x,double y) 26 { 27 return x<y?x:y; 28 } 29 double dis(node p,node q) 30 { 31 if (p.bel==q.bel) return oo; 32 return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)); 33 } 34 double make(int l,int r) 35 { 36 if (l==r) return oo; 37 int m=(l+r)/2,i,j,k,ll,rr,p,q,x,y,z,cnt=0; 38 double ans=min(make(l,m),make(m+1,r)); 39 for (i=l;i<=r;i++) 40 if (ab(a[i].x-a[m].x)<=ans) 41 temp[++cnt]=a[i]; 42 sort(temp+1,temp+cnt+1,cy); 43 for (i=1;i<=cnt;i++) 44 for (j=i+1;j<=cnt;j++) 45 { 46 if (temp[j].y-temp[i].y>ans) break; 47 ans=min(ans,dis(temp[i],temp[j])); 48 } 49 return ans; 50 } 51 int main() 52 { 53 int i,j,k,T; 54 scanf("%d",&T); 55 while (T--) 56 { 57 scanf("%d",&n); 58 for (i=1;i<=n;i++) 59 { 60 scanf("%lf%lf",&a[i].x,&a[i].y); 61 a[i].bel=0; 62 } 63 for (i=1;i<=n;i++) 64 { 65 scanf("%lf%lf",&a[i+n].x,&a[i+n].y); 66 a[i+n].bel=1; 67 } 68 sort(a+1,a+2*n+1,cx); 69 printf("%.3f\n",make(1,2*n)); 70 } 71 }