rt，从 AT_arc069_d 过来的

#include<bits/stdc++.h>
#define il inline
#define ls u<<1
#define rs u<<1|1
#define pb push_back
#define op(x) ((x)<=n?(x)+n:(x)-n)
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
const int N=2e4+5;
int n;
struct dat
{
	int pos,id;
	bool operator < (const dat &b) const
	{
		return pos<b.pos;
	}
	dat(int pos=0):pos(pos){}
}flag[N];
int tot,id[N<<2];
vector<int> g[N];
void build(int u,int l,int r)
{
	id[u]=++tot;
	if(l==r) return g[id[u]].pb(op(flag[l].id)),void();
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	g[id[u]].pb(id[ls]);
	g[id[u]].pb(id[rs]);
}
void link(int u,int l,int r,int x,int y,int p)
{
	if(y<l||r<x) return;
	if(x<=l&&r<=y) return g[p].pb(id[u]),void();
	int mid=(l+r)>>1;
	if(x<=mid) link(ls,l,mid,x,y,p);
	if(y>mid) link(rs,mid+1,r,x,y,p);
}
int tc,cnt,low[N],dfn[N],bel[N];
bool vis[N];
stack<int> stk;
void Tarjan(int u)
{
	low[u]=dfn[u]=++tc;
	vis[u]=1,stk.push(u);
	for(auto v:g[u])
		if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
			else if(vis[v]) low[u]=min(low[u],dfn[v]);
	if(low[u]==dfn[u])
	{
		++cnt;
		do
		{
			bel[u]=cnt;
			u=stk.top(),stk.pop();
			vis[u]=0;
		}while(low[u]^dfn[u]);
	}
}
bool check(int x)
{
	cnt=tc=0;
	clr(low),clr(dfn),clr(bel);
	build(1,1,tot=2*n);
	for(int i=1;i<=2*n;i++) g[i].clear();
	for(int i=1;i<=2*n;i++)
	{
		int l=upper_bound(flag+1,flag+1+2*n,dat(flag[i].pos-x))-flag;
		int r=upper_bound(flag+1,flag+1+2*n,dat(flag[i].pos+x-1))-flag-1;
		link(1,1,2*n,l,i-1,flag[i].id);
		link(1,1,2*n,i+1,r,flag[i].id);
	}
	for(int i=1;i<=2*n;i++)
		if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=n;i++)
		if(bel[i]==bel[i+n]) return false;
	return true;
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&flag[i].pos,&flag[i+n].pos);
			flag[i].id=i,flag[i+n].id=i+n;
		}
		sort(flag+1,flag+1+n*2);
		int l=0,r=flag[n*2].pos-flag[1].pos+1,ans=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(check(mid)) ans=mid,l=mid+1;
				else r=mid-1;
		}
		printf("%d\n",ans);		
	}
	return 0;
}