题目描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

每个输出结果占一行。
数据范围
1≤N≤100000,
0≤X,Y≤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

(暴力枚举) $O(nlogn)$

为啥没人写归并呢？其实还挺好写的，能优化就尽量优化吧.毕竟剪枝的复杂度太玄学了.

时间复杂度

O(nlogn)

参考文献

C++ 代码

//分治的典型例题吧,求最近的点对.
//我们考虑每次把点分开考虑,剩下的就是跨mid的.
//我们就得到的两边的答案,作为边界,把可能构成答案的点对找出来,暴力求解即可. 
#include<bits/stdc++.h>
using namespace std;
const int N=100010,qwq=1e8;
int T,n;
struct gg{double x,y,id;}a[N<<1],b[N<<1],t[N<<1];
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
inline bool cmp(gg x,gg y) {return x.x<y.x;}
inline void merge(int l,int mid,int r)
{
    int cnt=l;
    for(int i=l,j=mid+1;i!=mid+1||j!=r+1;)
    {
        if(i!=mid+1&&(j==r+1||a[i].y<=a[j].y)) b[cnt++]=a[i],++i;
        else b[cnt++]=a[j],++j;
    }
    for(int i=l;i<=r;++i) a[i]=b[i];
}
inline double dist(int i,int j)
{
    if(t[i].id==t[j].id) return qwq;
    double dx=t[i].x-t[j].x,dy=t[i].y-t[j].y;
    return sqrt(dx*dx+dy*dy);
}
inline double work(int l,int r)
{
    if(l==r) return qwq;
    int mid=l+r>>1;
    double ans=min(work(l,mid),work(mid+1,r));
    merge(l,mid,r);
    int cnt=0;
    for(int i=l;i<=r;++i)
        if(a[i].x<a[mid].x+ans&&a[i].x>a[mid].x-ans) t[++cnt]=a[i];
    for(int i=1;i<=cnt;++i)
    {
        for(int j=i+1;j<=cnt;++j)
        {
            if(t[j].y-t[i].y>=ans) break;
            ans=min(ans,dist(i,j));
        }
    }
    return ans;
}
int main()
{
    freopen("1.in","r",stdin); 
    T=read();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;++i) a[i].x=read(),a[i].y=read(),a[i].id=1;
        for(int i=n+1;i<=2*n;++i) a[i].x=read(),a[i].y=read(),a[i].id=2;
        n<<=1;
        sort(a+1,a+n+1,cmp);
        printf("%.3lf\n",work(1,n));
    }
    return 0;
}