思路是，先二分答案，然后线段树优化建图，然后判断二分图是否有完美匹配。

现在tle on 13，差不多再常数除以2就能过。

为了减小常数，使用了一个哈希判掉等价情况不重复算。

标算复杂度 $O(n^2)$ ,我的复杂度最坏情况下 $O(n\sqrt{n}log^3n)$ 。

试过改ISAP，更慢了。HLPP感觉小图表现不怎么样（？）

带binary search的题怎么能没有二分做法，等我卡过了就去发题解。Stop learning useless algorithms,go and solve some problems,learn how to use binary search.

#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=1e6;
int a[N],b[N];
int n,m,s,t,dis[M*2+N];
int h[M*2+N],cur[M*2+N],e[10000010],v[10000010],ne[10000010],idx,mx;
void add(int a,int b,int flow)
{
	e[idx]=b,v[idx]=flow,ne[idx]=h[a],h[a]=idx++;
}
bool bfs()
{
	for(int i=1;i<=n;i++)cur[i+M]=h[i+M],dis[i+M]=-1;
	for(int i=1;i<=mx;i++)cur[i]=h[i],dis[i]=-1; 
	cur[s]=h[s],cur[t]=h[t];
	dis[s]=0,dis[t]=-1;
    queue<int>Q;
    Q.push(s);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=h[u];~i;i=ne[i])
        {
        	if(!v[i])continue;
        	int j=e[i];
        	if(dis[j]==-1)
        	{
        		dis[j]=dis[u]+1;
        		if(j==t)return 1;
        		Q.push(j);
			}
		}
    }
    return 0;
}
int dfs(int u,int flow)
{
	if(u==t)return flow;
	int now=0;
	for(int i=cur[u];~i;i=ne[i])
	{
		if(now==flow)break;
		cur[u]=i;
		if(!v[i])continue;
		int j=e[i];
		if(dis[j]!=dis[u]+1)continue;
		int t=dfs(j,min(flow-now,v[i]));
		if(!t)dis[j]=-1;
		v[i]-=t,v[i^1]+=t,now+=t;
	}
	return now;
}
int Dinic()
{
	int sum=0;
	while(bfs())
	{
		int t;
		do
		{
			t=dfs(s,2147483647);
			sum+=t;
		}while(t);
	}
	return sum;
}
void clear(int u,int l,int r)
{
	if(l==r)
	{
		h[u]=h[t]=-1;
		return;
	}
	int mid=(l+r)>>1;
	h[u]=-1;
	clear(u<<1,l,mid),clear(u<<1|1,mid+1,r);
}
void build(int u,int l,int r)
{
	mx=max(mx,u);
	if(l==r)
	{
		add(u,t,1),add(t,u,0);
		return;
	}
	int mid=(l+r)>>1;
	add(u,u<<1,mid-l+1),add(u<<1,u,0);
	add(u,u<<1|1,r-mid),add(u<<1|1,u,0);
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void connect(int u,int l,int r,int L,int R,int x)
{
	if(L<=l&&R>=r)
	{
		add(x,u,R-L+1),add(u,x,0);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)connect(u<<1,l,mid,L,R,x);
	if(R>mid)connect(u<<1|1,mid+1,r,L,R,x);
}
int l[N],r[N];
const unsigned long long base=13331;
unordered_map<unsigned long long,int>mp;
bool check(int x)
{
	idx=mx=0;
	h[s]=-1;
	clear(1,1,n);
	build(1,1,n);
	for(int i=1;i<=n;i++)h[i+M]=-1;
	unsigned long long rz=0;
	for(int i=1;i<=n;i++)
	{
		add(s,i+M,1),add(i+M,s,0);
		int l=0,r=0;
		if(b[1]<=a[i]-x)
		{
			int L=1,R=n;
			while(L<R)
			{
				int mid=(L+R+1)>>1;
				if(b[mid]<=a[i]-x)L=mid;
				else R=mid-1;
			}
			l=L;
		}
		if(b[n]>=a[i]+x)r=lower_bound(b+1,b+1+n,a[i]+x)-b;
		if(r)r=max(r,l+1);
		if(l)connect(1,1,n,1,l,i+M);
		if(r&&(r<=n))connect(1,1,n,r,n,i+M);
		rz=rz*base+l;
		rz=rz*base+r;
	}
	if(mp[rz])return (mp[rz]==2);
	int ans=Dinic();
	if(ans==n)mp[rz]=2;
	else mp[rz]=1;
	return (ans==n);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	s=0,t=M+M;
	while(T--)
	{
		mp.clear();
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)cin>>b[i];
		sort(a+1,a+1+n);
		sort(b+1,b+1+n);
		int l=0,r=1e9;
		while(l<r)
		{
			int mid=(l+r+1)>>1;
			if(check(mid))l=mid;
			else r=mid-1;
		}
		cout<<l<<endl;
	}
	return 0;
}