最近点对距离问题

题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

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

输出格式

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

每个输出结果占一行。

输入输出样例 #1

输入 #1

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

1.414
0.000

输入输出样例 #2

输入 #2

1
3
1 1
2 2
3 3
4 4
5 5
6 6

输出 #2

2.828

限制条件

• $1 \le N \le 100000$
• $0 \le X, Y \le 1000000000$

样例解释 #1

第一个测试用例

核电站坐标：

1. $(0, 0)$
2. $(0, 1)$
3. $(1, 0)$
4. $(1, 1)$

特工坐标：

1. $(2, 2)$
2. $(2, 3)$
3. $(3, 2)$
4. $(3, 3)$

最近距离是特工 $(2, 2)$ 到核电站 $(1, 1)$ 的距离： $\sqrt{(2-1)^2 + (2-1)^2} = \sqrt{1 + 1} = \sqrt{2} \approx 1.414$

保留三位小数输出 $1.414$。

第二个测试用例

所有核电站和特工的坐标都是 $(0, 0)$，最近距离为 $0$，输出 $0.000$。

问题分析

这是一个经典的最邻近点对问题，但不是通常的在一个集合中找最近点对，而是在两个不同的点集之间找最近点对。

暴力方法（$O(N^2)$）对于 $N \le 100000$ 会超时，需要使用更高效的算法：

1. 分治法
2. KD-Tree
3. 使用最近点对思想的变种

对于两个点集之间的最近点对问题，可以：

1. 将所有点（核电站和特工）合并，但标记每个点属于哪个集合
2. 使用分治法找到最近点对
3. 如果找到的最近点对属于同一个集合，则需要继续寻找跨集合的最近点对
4. 实际上，可以分别处理两个集合，使用类似于最近点对的算法

由于坐标范围很大且 $N$ 很大，需要使用 $O(N \log N)$ 的算法。