POJ3714：求平面最近点对

寻找两个集合中的点的最近点对

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          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 node13 {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
         
          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 }