1.11 POJ 3714 Raid

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int MAXN = 200010;
 6 const double INF = 10000000000000.0;
 7 struct Point{
 8     double x, y;
 9     int flag;
10 }x[MAXN];
11 int y[MAXN], z[MAXN];
12 bool cmpx(const Point& a, const Point& b)
13 {   return a.x < b.x;   }
14 bool cmpy(const int& a, const int& b)
15 {   return x[a].y < x[b].y; }
16 inline double dis(const Point a, const Point b)
17 {   return a.flag ^ b.flag ? sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)) : INF;   }
18 
19 void Merge(int z[], int y[], int l, int r, int m)
20 {
21     int i = l, j = m+1, k = l;
22     while(i <= m && j <= r)
23         if(x[z[i]].y <= x[z[j]].y)    y[k++] = z[i++];
24         else    y[k++] = z[j++];
25     while(i <= m)   y[k++] = z[i++];
26     while(j <= r)   y[k++] = z[j++];
27 }
28 
29 double close(int y[], int z[], int l, int r)
30 {
31     if(l+1 == r)
32         return dis(x[l], x[r]);
33     if(l+2 == r)
34         return min(dis(x[l], x[l+1]), min(dis(x[l+1], x[r]), dis(x[l], x[r])));
35     int m = l+r>>1;
36     for(int i=l, j=m+1, k=l ; k<=r ; k++)
37         if(y[k] > m)    z[j++] = y[k];
38         else    z[i++] = y[k];
39     double res = min(close(z, y, l, m), close(z, y, m+1, r));
40     Merge(z, y, l, r, m);
41     int rt = l;
42     for(int i=l ; i<=r ; i++)
43         if(fabs(x[y[m]].x - x[y[i]].x) < res)
44             z[rt++] = y[i];
45     for(int i=l ; i<rt ; i++)
46         for(int j=i+1 ; j<rt ; j++)
47         {
48             if(x[z[j]].y - x[z[i]].y >= res)  break;
49             res = min(res, dis(x[z[j]], x[z[i]]));
50         }
51     return res;
52 }
53 
54 int main()
55 {
56     // freopen("input", "r", stdin);
57     int t, n;  scanf("%d", &t);
58     while(t--)
59     {
60         scanf("%d", &n);
61         for(int i=0 ; i<n ; i++)
62             scanf("%lf %lf", &x[i].x, &x[i].y), x[i].flag = 0, y[i] = i;
63         for(int i=n ; i<n<<1 ; i++)
64             scanf("%lf %lf", &x[i].x, &x[i].y), x[i].flag = -1, y[i] = i;
65         n <<= 1;
66         sort(x, x+n, cmpx);
67         sort(y, y+n, cmpy);
68         printf("%.3lf\n", close(y, z, 0, n-1));
69     }
70 }