题目描述
在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。
经过几天的苦思冥想，联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。
该系统由 N 个核电站提供能源，其中任意一个被摧毁都会使防御系统失效。
将军派出了 N 个特工进入据点之中，打算对能源站展开一次突袭。
不幸的是，由于受到帝国空军的袭击，他们未能降落在预期位置。
作为一名经验丰富的将军，亚瑟很快意识到需要重新安排突袭计划。
他现在最想知道的事情就是：
哪个特工距离任意一个发电站的距离最短？请计算这个最短距离是多少。
输入格式
- 输入包含多组测试用例。
- 第一行输入一个整数
T，表示测试用例的数量。
对于每个测试用例：
- 第一行输入一个整数
N，表示核电站和特工的数量。 - 接下来
N行，每行输入两个整数X Y，表示每个核电站的位置坐标。 - 再接下来
N行，每行输入两个整数X Y，表示每名特工的位置坐标。
输出格式
- 对于每个测试用例，输出一个浮点数，表示最近的距离，保留三位小数。
- 每个输出占一行。
数据范围
1 ≤ N ≤ 1000000 ≤ 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
这个就是最近点对问题
