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

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

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

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

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

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

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

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

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

本题采用二分和归并排序，定义一个结构题存储下标和属于兵还是属于能源，按照x坐标排序，，进入dfs再利用归并排序，按照y坐标排序，找出与中点线<res的点，再依次处理它们之间的距离

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

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

struct Point
{
    double x, y;
    bool type;
    bool operator < (const Point &w) const
    {
        return x < w.x;
    }
}point[N], temp[N];

double dist(Point a, Point b)
{
    if (a.type == b.type) return INF;
    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 = point[mid].x;//取出中点坐标
    double res = min(dfs(l, mid), dfs(mid + 1, r));//分别dfs选中最小的

    {
        int k = 0, i = l, j = mid + 1;
        //用y轴归并排序进入point，方便后续找到对应的6个点
        while (i <= mid && j <= r)
            if (point[i].y <= point[j].y) temp[k ++ ] = point[i ++ ];
            else temp[k ++ ] = point[j ++ ];
        while (i <= mid) temp[k ++ ] = point[i ++ ];
        while (j <= r) temp[k ++ ] = point[j ++ ];

        for (i = 0, j = l; i < k; i ++, j ++ ) point[j] = temp[i];
    }

    //找出距离中点线res的点
    int k = 0;
    for (int i = l; i <= r; i ++ )
        if (point[i].x >= mid_x - res && point[i].x <= mid_x + res)
            temp[k ++ ] = point[i];

    for (int i = 0; i < k; i ++ )
        for (int j = i - 1; j >= 0 && temp[i].y - temp[j].y <= res; j -- )
            res = min(res, dist(temp[i], temp[j]));

    return res;
}

int main()
{
    int T, n;
    cin >> T;
    while (T -- )
    {
        cin >> n;

        //输入坐标以及属于哪个队伍
        for (int i = 0; i < n; i ++ )
        {
            scanf("%lf%lf", &point[i].x, &point[i].y);
            //cin >> point[i].x >> point[i].y;
            point[i].type = 0;
        }
        for (int i = n; i < n * 2; i ++ )
        {
            scanf("%lf%lf", &point[i].x, &point[i].y);
            //cin >> point[i].x >> point[i].y;
            point[i].type = 1;
        }

        //按照横坐标排序
        sort(point, point + n * 2);

        printf("%.3f\n", dfs(0, n * 2 - 1));
    }
}