模板 稍加一点标记
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 200010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
int id;
int flag;
point(double x=,double y =):x(x),y(y){}
}p[N],pp[N],py[N];
typedef point pointt;
pointt operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
double dis(point a,point b)
{
if(a.flag==b.flag) return INF;
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b)
{
return a.x<b.x;
}
bool cmpp(point a,point b)
{
return a.y<b.y;
}
void binmerge(point py[],point pp[],int l,int m,int r)
{
int i,j,g=l;
for(i = l,j = m+ ; i <= m&&j <= r ;)
if(pp[i].y<pp[j].y) py[g++] = pp[i++];
else py[g++] = pp[j++]; while(i<=m) py[g++] = pp[i++];
while(j<=r) py[g++] = pp[j++];
memcpy(pp + l, py + l, (r - l + ) *sizeof(py[]));
}
double binshortest(point p[],point pp[],point py[],int l,int r)
{
if(r-l==) return dis(p[l],p[r]);
if(r-l==) return min(min(dis(p[l],p[r]),dis(p[l],p[l+])),dis(p[l+],p[r]));
int mid = (l+r)>>;
int i,j,g = l,o = mid+;
for(i = l ; i <= r ; i++)
{
if(py[i].id<=mid)//按y坐标顺序将点划分到pp左半数组
pp[g++] = py[i];
else
pp[o++] = py[i];//pp右半数组
}
double minz = min(binshortest(p,py,pp,l,mid),binshortest(p,py,pp,mid+,r));
binmerge(py,pp,l,mid,r);
g = l;
for(i = l ; i <= r ; i++)
if(fabs(py[i].x-py[mid].x)<minz) pp[g++] = py[i];
for(i = l ; i < g ; i++)
{
for(j = i+ ; j < g && fabs(pp[i].y-pp[j].y)<minz; j++)
minz = min(dis(pp[i],pp[j]),minz);
}
return minz;
}
int main()
{
int n,i,t;
cin>>t;
while(t--)
{
scanf("%d",&n);
for(i = ; i < n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
p[i].flag = ;
}
for(i = n; i < n*; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
p[i].flag = ;
}
n<<=;
sort(p,p+n,cmp);
for(i = ;i < n ;i++)
p[i].id = i;
memcpy(py,p,n*sizeof(py[]));
sort(p,p+n,cmpp);
double ans = binshortest(p,pp,py,,n-);
printf("%.3f\n",ans);
}
return ;
}