题目：https://arc069.contest.atcoder.jp/tasks/arc069_d
题意就是让你在n对数字每一对都选一个数使得任意两个数做差的绝对值最小值最大。
关系显然是一个2-sat，然后我们发现二份答案如果差值为x那么a-x+1到a+x-1是绝对不能选的，
也就是选完以后剩下的一定是这些，所以线段树优化连边覆盖区间。然后在线段树的底层端点再反过来一下即可。
By：大奕哥
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+;
int head[N],col[N],dfn[N],low[N],s[N],in[N],xx[N],yy[N],pos[N];
int n,c,rt,ans,cnt,tmp,num,pre,top;
struct tree{
int l,r;
}t[N<<];
struct edge{
int to,nex;
}e[N<<];
struct node{
int x,y;
bool operator <(const node &b)const{
return x<b.x;
}
}a[N];
void add(int x,int y)
{
e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;
}
void build(int &x,int l,int r)
{
if(l==r){
x=(a[l].y<=n)?a[l].y+n:a[l].y-n;
pos[a[l].y]=l;return;
}x=++num;
int mid=l+r>>;
build(t[x].l,l,mid);build(t[x].r,mid+,r);
add(x,t[x].l);add(x,t[x].r);
return;
}
void change(int x,int l,int r,int L,int R,int p)
{
if(L>R)return;
if(l==L&&r==R)
{
add(p,x);return;
}
int mid=l+r>>;
if(mid>=R)change(t[x].l,l,mid,L,R,p);
else if(L>mid)change(t[x].r,mid+,r,L,R,p);
else change(t[x].l,l,mid,L,mid,p),change(t[x].r,mid+,r,mid+,R,p);
return;
}
void dfs(int x)
{
dfn[x]=low[x]=++tmp;
s[++top]=x;in[x]=;
for(int i=head[x];i;i=e[i].nex)
{
int y=e[i].to;
if(!dfn[y])
{
dfs(y);
low[x]=min(low[x],low[y]);
}
else if(in[y])low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
c++;int a=-;
do{
a=s[top--];
in[a]=;
col[a]=c;
}while(a!=x);
}
return;
}
void init()
{
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(col,,sizeof(col));
tmp=c=;
return;
}
bool judge(int x)
{
init();
for(int i=;i<=n*;++i)head[i]=;cnt=pre;
for(int i=;i<=n;++i)
{
int AL=lower_bound(a+,a++*n,(node){xx[i]-x+,})-a;
int AR=upper_bound(a+,a++*n,(node){xx[i]+x-,})-a-;
if(AL<=AR)change(rt,,n*,AL,pos[i]-,i),change(rt,,n*,pos[i]+,AR,i);
int BL=lower_bound(a+,a++*n,(node){yy[i]-x+,})-a;
int BR=upper_bound(a+,a++*n,(node){yy[i]+x-,})-a-;
if(BL<=BR)change(rt,,n*,BL,pos[i+n]-,i+n),change(rt,,n*,pos[i+n]+,BR,i+n);
}
for(int i=;i<=num;++i)
if(!dfn[i])dfs(i);
for(int i=;i<=n;++i)
if(col[i]==col[i+n])return ;
return ;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
{
scanf("%d%d",&xx[i],&yy[i]);
a[i*-].x=xx[i];a[i*].x=yy[i];
a[i*-].y=i;a[i*].y=i+n;
}num=n*;
sort(a+,a++n*);
build(rt,,n*);
int l=,r=1e9;pre=cnt;
while(l<=r)
{
int mid=l+r>>;
if(judge(mid))ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
return ;
}