袭击

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 200010;
 4 double INF = 1e10;
 5 struct Point {
 6     double x, y;
 7     bool type;
 8 } points[N], temp[N];
 9 //temp是用于归并
10 bool cmp(Point p1, Point p2) {
11     return p1.x < p2.x;
12 }
13 double dist(Point a, Point b) {
14     if (a.type == b.type) {
15         return INF;
16     }
17     double dx = a.x - b.x;
18     double dy = a.y - b.y;
19     return sqrt(dx * dx + dy * dy);
20 }
21 double dfs(int l, int r) {
22     if (l >= r) {
23         return INF;
24     }
25     int mid = (l + r) / 2;
26     double mid_x = points[mid].x;
27     double res = min(dfs(l, mid), dfs(mid + 1, r));
28     {
29         int k = 0, i = l, j = mid + 1;
30         while (i <= mid && j <= r) {
31             if (points[i].y <= points[j].y) {
32                 temp[k++] = points[i++];
33             } else {
34                 temp[k++] = points[j++];
35             }
36         }
37         while (i <= mid) {
38             temp[k++] = points[i++];
39         }
40         while (j <= r) {
41             temp[k++] = points[j++];
42         }
43         for (i = 0, j = l; i < k; i++, j++) {
44             points[j] = temp[i];
45         }
46     }
47     int k = 0;
48     for (int i = l; i <= r; i++) {
49         if (points[i].x >= mid_x - res && points[i].x <= mid_x + res) {
50             temp[k++] = points[i];
51         }
52     }
53     for (int i = 0; i < k; i++) {
54         for (int j = i - 1; j >= 0 && temp[i].y - temp[j].y <= res; j--) {
55             res = min(res, dist(temp[i], temp[j]));
56         }
57     }
58     return res;
59 }
60 int main() {
61     int T;
62     cin >> T;
63     while (T--) {
64         int n;
65         cin >> n;
66         for (int i = 0; i < n; i++) {
67             cin >> points[i].x >> points[i].y;
68             points[i].type = 0;
69         }
70         for (int i = n; i < n * 2; i++) {
71             cin >> points[i].x >> points[i].y;
72             points[i].type = 1;
73         }
74         sort(points, points + n * 2, cmp);
75         cout << fixed << setprecision(3) << dfs(0, n * 2 - 1) << endl;
76     }
77     return 0;
78 }