袭击

在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。

依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。

经过几天的苦思冥想，联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。

该系统由 $N$ 个核电站供应能源，其中任何一个被摧毁都会使防御系统失效。

将军派出了 $N$ 个特工进入据点之中，打算对能源站展开一次突袭。

不幸的是，由于受到了帝国空军的袭击，他们未能降落在预期位置。

作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排突袭计划。

他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。

你能帮他算出来这最短的距离是多少吗？

输入格式

输入中包含多组测试用例。

第一行输入整数 $T$，代表测试用例的数量。

对于每个测试用例，第一行输入整数 $N$。

接下来 $N$ 行，每行输入两个整数 $X$ 和 $Y$，代表每个核电站的位置的 $X，Y$ 坐标。

在接下来 $N$ 行，每行输入两个整数 $X$ 和 $Y$，代表每名特工的位置的 $X，Y$ 坐标。

输出格式

每个测试用例，输出一个最短距离值，结果保留三位小数。

每个输出结果占一行。

数据范围

$1≤N≤100000$
$0≤X,Y≤1000000000$

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
2
1.414
0.000

题目分析

垫底抽风详细见这位佬的讲解，十分的详细，我觉得没什么需要补充的，如果不想看我就简短的说一下。

想要知道 $[l, r]$ 的两点之间最短值，那么我们只需要知道 $[l, mid]$ 和 $[mid + 1, r]$ 各自包含点的最短值 还有 $[l,mid], [mid + 1,r]$ 之间的最短值，然后取 $Min$ 即可。

前面两个很好解决，分治处理即可，问题是最后那个如何处理？

首先处理前两个，我们得到了一个两个区间包含的点的最短值 $tot$，最好处理的情况就是此时 $mid$ 上正好有一个点，若存在更优的情况 那只可能是在以 $mid$ 为圆心，$tot$ 为半径的一个圆内，所包含的所有点两两之间的距离。这样的点最多只会有 12 个（每边 6 个）。详细证明请看前面佬的证明，我这里就不证明了（懒得画图）

注意，我这里的代码很明显复杂度仍然不是最优的复杂度（也就是说还有hack的可能），因为 $[l, mid]$ 和 $[mid + 1, r]$ 之间的点已经处理过了，所以在处理时，只需要计算左边的点和右边的六个点之间的距离即可，也就是分两个数组保存左右区间的数再进行计算。

当然，目前的代码是足够通过题目了，接下来就看佬们如何hack了（随时更新）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cmath>
#include <cstdio>
#include <algorithm>

const int N = 200015;
struct node {
    double x, y;
    bool flag = false;
} arr[N], brr[N];
node temp[N];

int n, m;

bool cmp(node x, node y) {
    if(x.x == y.x) return x.y < y.y;
    else return x.x < y.x;
}

const int INF = 1e9;
double ans = (double)INF;

double dist(node x, node y) {
    if(x.flag == y.flag) return INF;
    else if(x.x == y.x && x.y == y.y && x.flag != y.flag) return x.flag < y.flag;
    else return (std::sqrt(((x.y - y.y) * (x.y - y.y)) + ((x.x - y.x) * (x.x - y.x))));
}

double dfs(int l, int r) {
    if(l >= r) return INF;
    
    int mid = (l + r) >> 1;
    //找到中间点
    double midx = arr[mid].x;
    //分治
    ans = std::min(dfs(l, mid), dfs(mid + 1, r));
    
    //分治最优排序方式（归并排序）
    {
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if(j > r || (i <= mid && arr[i].y <= arr[j].y)) temp[k] = arr[i++];
            else temp[k] = arr[j++];
        } for (int k = l; k <= r; k++) arr[k] = temp[k];
    }
    
    //找[l, mid] 与 [mid + 1, r] 之间点的最短距离
    //每边至多只有6个点 两边加起来12个点
    int k = 0;
    for (int i = mid; i >= l; i--) {
        if(arr[i].x >= midx - ans && arr[i].x <= mid + ans) {
            if(k == 6) break;
            temp[++k] = arr[i];
        }
    }
    
    for (int i = mid + 1; i <= r; i++) {
        if(arr[i].x >= midx - ans && arr[i].x <= mid + ans) {
            if(k == 12) break;
            temp[++k] = arr[i];
        }
    }
    
    //直接计算两点距离即可
    for (int i = 1; i <= k; i++) {
        for (int j = i - 1; j > 0 && temp[i].y - temp[j].y < ans; j--) {
            ans = std::min(ans, dist(temp[i], temp[j]));
        }
    } return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        ans = (double)INF; n = 1;
        scanf("%d", &m); 
        //不同的点打上不同的标记
        for (int i = 1; i <= m; i++) {
            scanf("%lf %lf", &brr[i].x, &brr[i].y);
            brr[i].flag = false;
        }
       
        for (int i = m + 1; i <= m * 2; i++) {
            scanf("%lf %lf", &brr[i].x, &brr[i].y);
            brr[i].flag = true;
        }
           
        std::sort(brr + 1, brr + 1 + 2 * m, cmp);
        
        bool flag = false;
        arr[1] = brr[1];
        //相同的点且坐标相同的点不需要加入计算的数组中
        //不同的点且坐标相同的点直接输出结果 没有比这个更小的距离了
        //不同的点且不同坐标的点直接加入计算的数组中即可，并且在这一步就直接计算距离
        for (int i = 2; i <= m * 2; i++) {
            if(brr[i].x == brr[i - 1].x && brr[i].y == brr[i - 1].y && brr[i].flag == brr[i - 1].flag) continue;
            else if(brr[i].x == brr[i - 1].x && brr[i].y == brr[i - 1].y && brr[i].flag != brr[i - 1].flag) {flag = true; puts("0.000"); break;}
            else {
                arr[++n] = brr[i];
                ans = std::min(ans, dist(arr[n], arr[n - 1]));
            }
        }
        
        if(flag) continue;
        else printf("%.3lf\n", dfs(1, n));
    } return 0;
}
算法
算法 分治

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！