//poj 3714 分治  TLE
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int MAXN = 100000 + 10;
const int INF = 0x3f3f3f3f;
int n, s;
double ans;
int mid, cnta, cnts;

struct node
{
	ll x, y;
} pa[MAXN];   //agent
node ps[MAXN];    //station

node tempa[MAXN];
node temps[MAXN];

double dist(node a, node b)
{
	double ans = sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
	return ans;	
}

bool cmp(node a, node b)
{
	if(a.x == b.x) return a.y < b.y;
	else return a.x < b.x;
}

bool cmpy(node a, node b)
{
	return a.y < b.y;
}

double jue(int a)
{
	if(a >= 0) return a;
	else return -a;
}

double solve(int lt, int rt)
{
	mid = (lt + rt) >> 1;
	ans = INF;
	
	if(lt == rt) return ans;
	if(lt+1 == rt) return min(dist(pa[lt], ps[rt]), dist(ps[lt], pa[rt]));
	
	ans = min(solve(lt, mid), solve(mid, rt));
	

	cnta = 0, cnts = 0;
	for(int i = lt; i <= rt; i++)
	{
		if(jue(pa[mid].x-pa[i].x) <= ans) tempa[++cnta] = pa[i];
		if(jue(ps[mid].x-ps[i].x) <= ans) temps[++cnts] = ps[i];
	}
	
//	sort(tempa+1, tempa+1+cnta, cmpy);
//	sort(temps+1, temps+1+cnts, cmpy);
	
	for(int i = 1; i <= cnta; i++)
		for(int j = 1; j <= cnts; j++)
		{
//			if(jue((temps[j].y - tempa[i].y)) > ans) break;
			ans = min(ans, dist(pa[i], ps[j]));
		}
	
	return ans;	
}

int main()
{
	cin >> s;
	while(s--)
	{
		memset(pa, 0, sizeof(pa));
		memset(ps, 0, sizeof(ps));
		
		cin >> n;
		for(int i = 1; i <= n; i++) cin >> pa[i].x >> pa[i].y;
		for(int i = 1; i <= n; i++) cin >> ps[i].x >> ps[i].y;
		
		sort(pa+1, pa+1+n, cmp);
		sort(ps+1, ps+1+n, cmp);
		
		double res = solve(1, n);
		printf("%.3f\n", res);		
	}
	return 0;
} 

• Re:自己拍了上百组大数据都没错，但是死活WA (17) Jayfeather 2019-07-18 19:47:03
• Re:自己拍了上百组大数据都没错，但是死活WA (2032) zhuowenliang 2023-12-20 17:23:58