算法进阶指南 袭击

题目描述

在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。

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

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

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

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

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

他现在最想知道的事情就是：

哪个特工距离任意一个发电站的距离最短？请计算这个最短距离是多少。

输入格式

• 输入包含多组测试用例。
• 第一行输入一个整数 T，表示测试用例的数量。

对于每个测试用例：

1. 第一行输入一个整数 N，表示核电站和特工的数量。
2. 接下来 N 行，每行输入两个整数 X Y，表示每个核电站的位置坐标。
3. 再接下来 N 行，每行输入两个整数 X Y，表示每名特工的位置坐标。

输出格式

• 对于每个测试用例，输出一个浮点数，表示最近的距离，保留三位小数。
• 每个输出占一行。

数据范围

• 1 ≤ N ≤ 100000
• 0 ≤ X, Y ≤ 1,000,000,000

输入样例

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

c++代码

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;
int T, N;

class node{
public:
    double i;
    double j;
    int sym;
};

bool sort_by_x(node a, node b) {
    return a.i < b.i;
}

bool sort_by_y(node a, node b) {
    return a.j < b.j;
}

double op(double x1, double y1, double x2, double y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

double recent_questions(vector<node>& arr, int l, int r) {
    if (l >= r) return DBL_MAX;
    if (r - l == 1) {
        if (arr[l].sym == arr[r].sym) return DBL_MAX;
        return op(arr[l].i, arr[l].j, arr[r].i, arr[r].j);
    }
    int mid = (l + r) / 2;
    double res = min(recent_questions(arr, l, mid), recent_questions(arr, mid + 1, r));
    vector<node> tem;
    for (int i = l; i <= r; i++) {
        if ((arr[i].i - arr[mid].i) * (arr[i].i - arr[mid].i) <= res) tem.push_back(arr[i]);
    }
    sort(tem.begin(), tem.end(), sort_by_y);
    for (int i = 0; i < tem.size(); i++) {
        for (int j = i + 1, cont = 0; j < tem.size() && cont < 7; j++, cont++) {
            if (tem[i].sym != tem[j].sym) {
                res = min(res, op(tem[i].i, tem[i].j, tem[j].i, tem[j].j));
            }
        }
    }
    return res;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
        vector<node> arr(2 * N);
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &arr[i].i, &arr[i].j);
            arr[i].sym = 0;
        }
        for (int i = N; i < 2 * N; i++) {
            scanf("%lf %lf", &arr[i].i, &arr[i].j);
            arr[i].sym = 1;
        }
        sort(arr.begin(), arr.end(), sort_by_x);
        printf("%.3lf\n", sqrt(recent_questions(arr, 0, 2 * N - 1)));
    }
    return 0;
}//by wqs

这个就是最近点对问题