题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

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

输出格式

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

每个输出结果占一行。

数据范围

$1 \leq N \leq 100000,$
$0 \leq X, Y \leq 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

算法1

(分治) $\mathcal O(n \log n)$

我们先考虑只有一种点，找两个距离最近的点的情况，然后再拓展到找两种点中的最近距离的情况。

若只有一种点，那么先将所有点按 $X$ 坐标排序。

让左指针 $left$ 指向最左边的点的下标，右指针 $right$ 指向最右边的点的下标，$mid$ 指向中间点的下标。
分别处理 $[left, mid]$ 和 $[mid + 1, right]$ 两段区间的最近点对。

记 $[left, right]_{min}$ 为区间 $[left, right]$ 中的最近点对距离
则 $[left, right] _ {min} = min({[left, mid] _ {min},[mid + 1, right] _ {min},[left, mid] 中选一个点与[mid + 1, right] 中选一个点的最近距离})$

如果能分治处理出 [left, mid] 中选一个点与 [mid + 1, right] 中选一个点的最近距离，就能分治处理出 $[left, mid] _ {min}$ 和 $[mid + 1, right] _ {min}$，那么也就可以求出 $[left, right] _ {min}$ 了。

我们先假定答案 $ans = min([left, mid], [mid + 1, right])$，然后考虑什么情况还能使答案更新。
先考虑从左边选一个点，那么只有当右边存在一个点，使得这两点距离 $< ans$ 时才会更新 $ans$。
那么我们可以从左边选一个点，以 $ans$ 为半径画一个圆，看是圆内是否存在一个点在 $[mid + 1, right]$ 中。
那所有的距离中点的 $x$ 距离超过 $ans$ 的点就都可以不处理了。

这说的有点抽象哈，我再放张图

对于上图中红色的点，若 $ans = min([left, mid] _ {min}, [mid + 1, right] _ {min})$，那么我们只需要考虑阴影部分面积中的点即可。

这里还有一个很强的性质，使我们可以在 $\mathcal O(n)$ 的时间复杂度之内求出左边一个点，右边一个点的情况

每处理一个左边的点时，右边最多只会有 $6$ 个点被考虑到

证明：

首先考虑极端情况，即该点正好在分界线 $mid$ 上

圆形不是很好考虑，我们考虑下图橙色矩形中所有的点。

若该矩形中存在的点不超过 $6$ 个，那么所有考虑的点的数量也就不超过 $6$ 个。

我们将该矩形划分为以下 $6$ 个部分，

反证法，假设会有 $7$ 个点及以上会在我们考虑范围内，那么根据抽屉原理，在上面 $6$ 个部分中，至少会有一个部分，包含两个在我们考虑范围内的点。
由于每个矩形部分都是相同的，所以我们不妨假设第一个矩形中包含两个在我们考虑范围内的点。

那么由于这两个点都在同一个矩形中，这两个点的距离就一定小于该矩形的对角线长度。
而该矩形的对角线长度即为 $\displaystyle r \sqrt{(\frac 2 3) ^ 2 + (\frac 1 2) ^ 2} = r \sqrt{\frac 4 9 + \frac 1 4} = \frac 5 6 r < r = ans$
也就是说，如果两个点在同一个矩形中，那么这两个点的距离就一定小于 $ans$，不符合 $ans = min([left, mid] _ {min}, [mid + 1, right] _ {min})$，故不成立。

$QED$

所以每次在处理左边的点时，最多只会考虑 $6$ 个右边的点，总的时间复杂度最坏是 $O(6n)$，可以接受。

该题是处理两类点的最短距离。
我们需要在每个点上，记录一个 $type$，也就是它的类型。
那么如果两个点的 $type$ 相同，在计算时将这两个点的距离制为正无穷。
详见代码注释。

时间复杂度

分治中一共会分治 $\log n$ 层，
每层分治的时间复杂度最多是 $\mathcal O(n)$
所以总的时间复杂度是 $\mathcal O(n \log n)$

注意我原来的代码时间复杂度应该是平方级别的
（但是数据过水，我的代码侥幸过了）
这里感谢楼下巨佬指出错误

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath> // 计算距离时需要用到 sqrt 函数

using namespace std;

const int N = 200005;
const double INF = 1e15;
const double eps = 1e-6;

int n;
double mind;
struct point // 结构体存所有点
{
    double x, y;                           // 存每个点的坐标
    bool type;                             // 存每个点的类型
    bool operator < (const point &t) const // 用于将所有点按 x 坐标从小到大排序
    {
        return x < t.x;
    }
} points[N], tmp[N];  // points 存输入的每个点，tmp 存分治时对于每个点要处理的点

double get_dist(point a, point b)            // 返回点 a 和点 b 的直径距离
{
    if (a.type == b.type) return mind ;      // 如果这两个点的类型不同，返回当前最优答案即可。
    double dx = a.x - b.x, dy = a.y - b.y;   // 计算出这两个点横纵坐标的差值
    return sqrt(dx * dx + dy * dy);          // 返回这两个点的平面距离
}

double dfs(int l, int r)
{
    if (l == r) return INF ;                 // 如果剩下区域只有一个点，那么为了避免更新答案，返回正无穷
    int mid = l + r >> 1;                    // 找到剩下区域内中间的点的位置。
    double mid_x = points[mid].x;            // 取出该点的 x 坐标，与该坐标距离超过 ans 的点不计入考虑。
    double ans = min(dfs(l, mid), dfs(mid + 1, r)); // 分治计算出上述未被更新的 ans

    // 先将 points 中的 [l, mid] 和 [mid + 1, r] 两段进行按 y 轴坐标进行按序归并
    // 注意这里一定要归并，后面对于每个点我们才能快速找出对应的（至多） 6 个点，以保证总时间复杂度是 O(n log n)
    int i = l, j = mid + 1, cnt = 0;
    while (i <= mid && j <= r)
        if (points[i].y < points[j].y) tmp[cnt ++ ] = points[i ++ ];
        else    tmp[cnt ++ ] = points[j ++ ];
    while (i <= mid) tmp[cnt ++ ] = points[i ++ ];
    while (j <= r) tmp[cnt ++ ] = points[j ++ ];
    for (i = l; i <= r; i ++ ) points[i] = tmp[i - l];

    // 找到所有在 [mid_x - ans, mid_x + ans] 中的点，存入 tmp
    cnt = 0;
    for (i = l; i <= r; i ++ )
        if (points[i].x >= mid_x - ans && points[i].x <= mid_x + ans) // 如果说该点距离 mid_x 的距离小于 ans，那么需要考虑该点
            tmp[cnt ++ ] = points[i];
    // 下面第二层循环中，有 tmp[i].y - tmp[j].y <= ans 这个判断，才能保证我们对于每个点最多只考虑六个点
    // 这样在每层递归中，就可以保证时间复杂度是线性的，否则时间复杂度是平方级别的
    for (i = 0; i < cnt; i ++ ) // 处理所有 tmp 中的点
        for (j = i - 1; ~j && tmp[i].y - tmp[j].y + eps <= ans; j -- )
            ans = min(ans, get_dist(tmp[i], tmp[j])); // 更新 ans
    mind = min(mind, ans);
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            scanf("%lf %lf", &points[i].x, &points[i].y); // 输入所有核电站的坐标
            points[i].type = false;                       // 核电站的 type 制成 false
        }
        for (int i = n; i < n << 1; i ++ )
        {
            scanf("%lf %lf", &points[i].x, &points[i].y); // 读入所有特工的坐标
            points[i].type = true;                        // 特工的 type 制成 true
        }
        mind = get_dist(points[0], points[(n << 1) - 1]);
        sort(points, points + (n << 1));                  // 将所有点按 x 坐标排序
        printf("%.3lf\n", dfs(0, (n << 1) - 1));          // 分治函数的返回值即为答案
    }
    return 0;
}