C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 201000;
const double INF = 1e10;

struct node
{
    double x, y;
    bool type;
}p[maxn], temp[maxn]; 

bool cmp(node a, node b) //因为不太懂内联函数所以就最基础的sort+cmp
{
    return a.x < b.x;
}

double dis(node a, node b) //求两点距离
{
    if(a.type == b.type) return INF;
    double dis_y = a.y - b.y;
    double dis_x = a.x - b.x;
    return sqrt(dis_y*dis_y + dis_x*dis_x);
}

double dfs(int l, int r)
{
    if(l >= r) return INF; //当前区间只有一个元素的时候
    int mid = (l + r)>> 1;  //求出当前区间的中间值
    double mid_x = p[mid].x; //将中间值的x值作为 分割线
    double res = min(dfs(l,mid),dfs(mid+1,r)); //以分割线分别遍历两边的区间

    {    //将区间内的y归并排序
        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r)
        {
            if(p[i].y <= p[j].y) temp[k ++] = p[i ++];
            else    temp[k ++] = p[j ++];
        }
        while(i <= mid) temp[k ++ ] = p[i ++];
        while(j <= r) temp[k ++] = p[j ++];

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

    int k = 0;
    for(int i = l; i <= r; i ++)
    {
        if(p[i].x <= mid_x + res && p[i].x >= mid_x-res) //遍历当前区间的点，如果该点的x在分割线左右
                                                        //res最小距离之内的 记录下来
        temp[k ++] = p[i];
    }

    for(int i = 0; i < k; i ++)                 //遍历记录下来的点
    {   
        for(int j = i-1; j >= 0 && temp[i].y-temp[j].y <= res; j --)//遍历之前的点
        {                                                           //如果之前的点与当前点y的距离小于最小距离
            res = min(res,dis(temp[i],temp[j]));//那么我们更新目前最小距离
        }
    }

    return res; //遍历完成后就是最小的距离， 我们返回输出即可
}

int main()
{
    int t ;
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        for(int i = 0; i < n; i ++)
        {
            cin >> p[i].x >> p[i].y;
            p[i].type = 0;
        }
        for(int i = n; i < 2*n; i ++)
        {
            cin >> p[i].x >> p[i].y;
            p[i].type = 1;
        }
        sort(p,p+2*n,cmp);
        printf("%.3f\n",dfs(0,2*n-1)); //遍历所有的点
    }
    return 0;
}