AcWing-119-袭击

问题

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

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

输出格式

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

每个输出结果占一行。

数据范围

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

输入样例：

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.414
0.000

思路

分治法，将所有点先按照 x 轴排序，再进行分析。将其从中间分为两个部分，则最终的结果可由下面三部分组成：

1. 区间[l, mid]中的最小距离点对
2. 区间[mid+1, r]中的最小距离点对
3. 区间[l, mid]的点和区间[mid+1,r]中的点的最小距离点对

选择三个部分中的最小值即为最终答案。

此外，当左右两个区间的答案计算出来之后（设两个区间的到的最小值为 res），显然可以知道，在 x = mid为中心，x = mid - res 和 x = mid + res为两个端点所围成的范围内存在的点之间的最小距离，才可能存在比 res 更小的值，考虑此范围外的点无意义。因此，需要在计算了两区间的最小距离之后，对上述的３点进行计算的时候，缩小范围到 [mid-res, mid+res]区间内的点进行计算。

题解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int MAX = 200010;
const double INF = 1e10;

int n, t;

struct Point {
    int x, y;
    bool type;  //两种不同组的点

    bool operator<(const Point &w) const {  //运算符重载
        return x < w.x;
    }
} points[MAX], temp[MAX];

double dist(Point &a, Point &b) {
    if (a.type == b.type) return INF;   //同组返回无穷大
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

double dfs(int l, int r) {
    if (l >= r) return INF;

    int mid = l + r >> 1;
    double mid_x = points[mid].x;   //中间点
    double res = min(dfs(l, mid), dfs(mid + 1, r));

    {   //归并排序的 merge 函数，按照 y 轴排序
        int k = l, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (points[i].y <= points[j].y) temp[k++] = points[i++];
            else temp[k++] = points[j++];
        }
        while (i <= mid) temp[k++] = points[i++];
        while (j <= r) temp[k++] = points[j++];

        for (int m = l; m <= r; ++m) points[m] = temp[m];
    }

    //筛选出在两条边界线[mid_x-res, min_x+res]内的点
    int k = 0;
    for (int i = l; i <= r; ++i) {
        if (points[i].x >= mid_x - res && points[i].x <= mid_x + res) temp[k++] = points[i];
    }

    //遍历在两条边界范围内的点，求两两之间的距离最小值
    for (int i = 0; i < k - 1; ++i) {
        for (int j = i + 1; j < k && temp[i].y - temp[j].y <= res; ++j) {
            res = min(res, dist(temp[i], temp[j]));
        }
    }

    return res;
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int j = 0; j < n; ++j) {       //核电站
            scanf("%d%d", &points[j].x, &points[j].y);
            points[j].type = false;
        }
        for (int j = n; j < n * 2; ++j) {   //特工
            scanf("%d%d", &points[j].x, &points[j].y);
            points[j].type = true;
        }

        sort(points, points + n * 2);   //按照横坐标排序
        printf("%.3lf\n", dfs(0, n * 2 - 1));
    }

    return 0;
}