题目描述

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

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

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

该系统由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

二分

如果只是一堆点，求两个点距离最小值，那么进行分治
将这堆点按照横坐标排序，分为左右两堆，分别求出两堆各自的距离最小值，再求出，当点在两边的时候最小值是什么

设两堆各自得到的最小距离的最小值为δ，设左右两堆的分割线为x=x’,则只需要在[x’-δ,x’+δ]中寻找最小值。设在此区间内的某一点坐标为(x,y),最小距离的点应该在以此点为圆心的圆域内(扩展一下，变为与此圆外接的正方形)。考察此点以右的矩形区域，可以证得，此区域中最多有6个点。

每一个小矩形块的长宽分别为2δ/3，δ/2,则对角线长度<δ，所以每一个小矩形中不可能同时存在两个点，否则两堆中的最小距离不可能为δ，所以，此矩形区域中最多有六个点

所以再从此点向上按纵坐标排序取6个点取距离最小值即可

可以在递归的时候就把每一堆按纵坐标排序，再利用归并，最后就是一个有序链表，可以直接拿到在上下δ之间的点

这里是两堆不一样的点，可以合在一起，如果是同一类点距离为正无穷，否则计算距离

Tip：如果很不幸，在分为两堆后，两类点刚好在两堆，没有交集，那么时间复杂度会变成n^2,因为每个点都要各自算一遍，这时，可以将横纵坐标随机旋转一个角度(旋转矩阵为：[cosθ,-sinθ;sinθ,cosθ],具体推导，这篇文章可以参考 https://blog.csdn.net/yinhun2012/article/details/79544205 )，那么就可以使两堆有交集，而旋转后距离是不变的，只是相当于找了另外一条直线作为分割线而不是传统的与x或y轴平行的直线

C++ 代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

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

struct Point{
    double x,y;
    bool type;
    bool operator<(const Point &w) const{
        return x<w.x;
    }
}points[N],temp[N];//归并需要辅助数组temp

double dist(Point a,Point b){
    if(a.type==b.type)    return INF;
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
double dfs(int l,int r){
    if(l>=r)  return INF;//l>=r说明当前区间最多只有一个元素
    int mid=(l+r)>>1;
    double div=points[mid].x;
    double res=min(dfs(l,mid),dfs(mid+1,r));
    //对y进行归并排序(可以不用，注释掉也能过)
    {
        int k=0,i=l,j=mid+1;//k是记录排的个数，i是左边点的开头，j是右边点的开头
        while(i<=mid&&j<=r){
            if(points[i].y<points[j].y)    temp[k++]=points[i++];
            else    temp[k++]=points[j++];
        }
        while(i<=mid)    temp[k++]=points[i++];
        while(j<=r)    temp[k++]=points[j++];

        for(i=0,j=l;i<k;i++,j++)     points[j]=temp[i];
    }
    //取出在div左右两侧δ的所有点
    int k=0;
    for(int i=l;i<=r;i++){
        if(points[i].x>=div-res&&points[i].x<=div+res)    temp[k++]=points[i];
    }
    //计算取出来的点与上（下）两侧δ中点的距离
    for(int i=0;i<k;i++){
        for(int j=i+1;j<k&&temp[j].y-temp[i].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++){
            cin>>points[i].x>>points[i].y;
            points[i].type=0;
        }
        for(int i=n;i<2*n;i++){
            cin>>points[i].x>>points[i].y;
            points[i].type=1;
        }
        sort(points,points+2*n);
        printf("%.3f\n",dfs(0,2*n-1));
    }
    return 0;
}