改了5个小时！！！现在很暴躁！！！
第三个样例输出了39。

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int N = 4e5 + 10;
const int Mod = 998244353;

inline int read() {
    int x;
    scanf("%d",&x);
    return x;
}

int n;
struct Node {
    int pos,id;
} a[N];
bool operator<(Node x,Node y) {
    return x.pos<y.pos;
}

vector<int>G[N];

inline void insert(int x,int y) {
//    cout<<"add"<<x<<' '<<y<<endl;
    G[x].push_back(y);
}

int dfn[N],low[N],dfc;
int color[N],tot;
int InStack[N];
stack<int>stk;

void tarjan(int x) {
    dfn[x]=low[x]=++dfc;
    stk.push(x);
    InStack[x]=true;
    for(int y:G[x]) {
        if(!dfn[y]) {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        } else if(InStack[y]) {
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(dfn[x]==low[x]) {
        tot++;
        while(stk.top()!=x) {
            color[stk.top()]=tot;
            InStack[stk.top()]=false;
            stk.pop();
        }
        color[x]=tot;
        InStack[x]=false;
        stk.pop();
    }
}

int ls[N],rs[N],siz;
int rt;//父连子
int leaf[N];
#define ls ls[pos]
#define rs rs[pos]
void build(int &pos,int l,int r) {
    pos=++siz;
    ls=0;
    rs=0;
    if(l==r) {
        leaf[l]=pos;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    insert(pos,ls);
    insert(pos,rs);
}
//单点连区间
void add(int pos,int l,int r,int ql,int qr,int qpos) {
    if(ql<=l&&r<=qr) {
        insert(qpos,pos);
        return;
    }
    int mid=(l+r)>>1;
    if(ql<=mid) add(ls,l,mid,ql,qr,qpos);
    if(mid+1<=qr) add(rs,mid+1,r,ql,qr,qpos);
}
#undef ls
#undef rs

bool check(int mid) {
    dfc=0;
    tot=0;
    for(int i=1; i<=siz; i++) G[i].clear();
    siz=2*n;
    build(rt,1,2*n);
    for(int i=1; i<=2*n; i++) {
        insert(leaf[i],a[i].id);
    }
    for(int i=1; i<=siz; i++) dfn[i]=low[i]=0;

    for(int i=1; i<=2*n; i++) {
        int l=lower_bound(a+1,a+2*n+1,(Node) {a[i].pos-mid+1,0})-a;
        int r=upper_bound(a+1,a+2*n+1,(Node) {a[i].pos+mid-1,0})-a-1;
//        cout<<a[i].pos<<"?\n";
//        for(int j=l; j<=r; j++)
//            cout<<a[j].pos<<' ';
//        cout<<endl;
        if(l<=i-1) add(rt,1,2*n,l,i-1,i);
        if(i+1<=r) add(rt,1,2*n,i+1,r,i);
//		for(int j=1;j<=2*n;j++)
//		{
//			if(a[i].pos-mid<a[j].pos&&a[j].pos<a[i].pos+mid)
//				add(rt,1,2*n,j,j,i);
//		}
    }

    for(int i=1; i<=siz; i++) 	
		if(!dfn[i]) 
			tarjan(i);
    for(int i=1; i<=n; i++)
        if(color[i]==color[i+n])
            return false;
    return true;
}

int main() {
//    freopen("1.in","r",stdin);
    n=read();
    for(int i=1; i<=n; i++) {
        a[i].pos=read();
        a[i].id=i+n;
        a[i+n].pos=read();
        a[i+n].id=i;
    }
    sort(a+1,a+2*n+1,[](Node x,Node y) {
        return x.pos<y.pos;
    });
//    for(int i=1;i<=100;i++)
//	{
//
// cout<<check(i)<<' ';
//	}
    int l=0,r=1e9;
    while(l+1<r) {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }	 
    if(check(r)) cout<<r;
    else cout<<l;
    return 0;
}