#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=200010,INF=1e7;//定义数据范围和最大值
struct Point{
double x,y;
bool type;
bool operator<(const Point &w)const
{
return x<w.x; //结构体内重置运算符,使有关Point 的<的运算都变为 x<w.x的运算
}
};
Point points[maxn],temp[maxn];
double dist(Point a, Point b)
{ //计算两个结点的二维坐标上的距离
if(a.type==b.type)
return INF;//当两结点同属一个阵营时,不是所求答案,所以返回无限大距离
double sx=a.x-b.x,sy=a.y-b.y;
return sqrt(sx*sx+sy*sy);
}
double dfs(int l,int r)
{ //利用分治法解决该问题
if(l>=r)
return INF;
int mid=l+r>>1;
double res=min(dfs(l,mid),dfs(mid+1,r));
//在得到左右两边的整体的最小距离后考虑特殊情况在分界线两侧可能的情况
//因此筛选的点都应该在分界线线两侧res范围内找,因为在扩大后的范围中两侧的距离是一定大于res的即不用考虑
//还能在这筛选出来的点中在优化:
//首先思考我们得到所有点后应该送第一点开始遍历其余点,然后再从第二点开始遍历其余点分别计算其距离然后比较得到最小值
//我们优化的方法是由得到的点以纵坐标排序,然后在利用上条方法计算距离时,若距离开始大于res时,则不用循环了
//因为只要纵坐标大于res后两点总的距离是一定大于res的即不用再计算判断了
//这里在补充一下,有人可能会问了为什么不用横坐标排序,原因时已经由 double res=min(dfs(l,mid),dfs(mid+1,r));
//得到了分界线单纯的两侧中最小的距离为res,那么再在mid-res~mid+res中对横坐标进行排序是没有意义的
//下面我们利用归并拍寻对纵坐标进行排序
{
int k=0,i=l,j=mid+1;
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];
}
int k=0;
//筛选符合条件的点
for(int i=l;i<=r;i++)
if(points[i].x<=points[mid].x+res&&points[i].x>=points[mid].x-res)
temp[k++]=points[i];
//利用优化后的算法计算筛选出来的位于分界线两端res距离的点中的最小距离
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++)
{
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("%.3lf\n",dfs(0,2*n-1));
}
return 0;
}