Language: C++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 2e4+100;
const int INF = 1e9+1;
inline int read()
{
	int x = 0 , f = 1 ; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') f = -f ; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0' , c = getchar();
	return x * f;
}
int n , cnt;
int head[N];
struct node{
	int to , nex;
	node(int to = 0 , int nex = 0):to(to) , nex(nex){}
}e[N*40000];

struct Node{
	int val , id;
	Node(int val = 0 , int id = 0):val(val) , id(id){}
	bool operator < (const Node &A) const { return val < A.val; }
}a[N];

void add(int u , int v) { e[++cnt] = node(v , head[u]); head[u] = cnt; }

int dfn[N] , low[N] , sta[N] , col[N] , pos[N] , L[N] , R[N] , len, top , num , tot;
bool vis[N];

void Tarjan(int x)
{
	dfn[x] = low[x] = ++tot; sta[++top] = x; vis[x] = true;
	for(int i = head[x] ; i ; i = e[i].nex)
	{
		int to = e[i].to;
		if(!dfn[to]) Tarjan(to) , low[x] = min(low[x] , low[to]);
		else if(vis[to]) low[x] = min(low[x] , dfn[to]);
	}
	if(low[x] == dfn[x])
	{
		num++;
		int t;
		do{
			t = sta[top--];
			col[t] = num; vis[t] = false;
		}while(t != x);
	}
}

inline int Abs(int x) { return x < 0 ? -x : x; }

void Add(int l , int r , int to)
{
	if(l > r) return;
	if(pos[l] == pos[r])
	{
		for(int i = l ; i <= r ; ++i) add(a[i].id , to);
		return ;
	}
	for(int i = l ; i <= R[pos[l]] ; ++i) add(a[i].id , to);
	for(int i = L[pos[r]] ; i <= r ; ++i) add(a[i].id , to);
	for(int i = pos[l] + 1 ; i <= pos[r] - 1 ; ++i) add(i + (n << 1) , to);
}

bool check(int k)
{
	memset(dfn , 0 , sizeof dfn); memset(vis , false , sizeof vis);
	memset(low , 0 , sizeof low); memset(col , 0 , sizeof col);
	memset(head, 0 , sizeof head); tot = 0 , cnt = 0 , num = 0 , top = 0;
	
	for(int i = 1 ; i <= pos[n<<1]; ++i)
		for(int j = L[i] ; j <= R[i] ; ++j) add(i + (n << 1) , a[j].id);
		
	for(int i = 1 ; i <= (n<<1) ; ++i)
	{
		int opt = a[i].id <= n ? a[i].id + n : a[i].id - n;
		int l = lower_bound(a + 1 , a + 1 + (n << 1) , Node(a[i].val - k , i)) - a;
		int r = lower_bound(a + 1 , a + 1 + (n << 1) , Node(a[i].val + k , i)) - a;
		int lr = lower_bound(a + 1 , a + 1 + (n << 1) , a[i] ) - a , rr = lr;
		while(a[lr].val == a[i].val) lr--;
		while(a[rr].val == a[i].val) rr++;
		while(a[i].val - a[l].val > k && l <= r) l++;
		while(a[r].val - a[i].val > k && l <= r) r--;
		if(!(l <= r)) continue;
		for(int j = lr + 1 ; j <= rr - 1 ; ++j) if(a[j].id != a[i].id) add(a[j].id , opt);
		Add(l , lr , opt); Add(rr , r , opt);
	}
	for(int i = 1 ; i <= (n<<1) ; ++i) if(!dfn[i]) Tarjan(i);
	for(int i = 1 ; i <= n ; ++i) if(col[i] == col[i+n]) return false;
	return true;
}

// 原节点 1 ~ 2n 块 2n + 1 ~ 2n + pos[n]
int main()
{
//	freopen("disaster.in" , "r" , stdin);
//	freopen("disaster.out" , "w" , stdout);
	n = read(); len = sqrt(n << 1);
	for(int i = 1 ; i <= n ; ++i) a[i] = Node(read() , i) , a[i+n] = Node(read() , i+n);
	sort(a + 1 , a + 1 + (n << 1));
	for(int i = 1 ; i <= (n << 1); ++i) pos[i] = (i-1) / len + 1;
	for(int i = 1 ; i <= pos[n<<1] ; ++i) L[i] = (i-1) * len + 1 , R[i] = min(i * len , n << 1 );
	int l = 1 , r = INF , ans = -1;
	while( l <= r )
	{
		int mid = (l + r) >> 1;
		if(check(mid)) ans = mid , l = mid + 1;
		else		   r = mid - 1;
	}
	cout << ans+1 << endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
3
1 2 
3 4 
5 6
*/

Compiler output:
/tmp/cczN2fu3.o: in function `Tarjan(int)':
a.cc:(.text+0x92): relocation truncated to fit: R_X86_64_PC32 against symbol `tot' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0x9b): relocation truncated to fit: R_X86_64_PC32 against symbol `tot' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0xa1): relocation truncated to fit: R_X86_64_PC32 against symbol `tot' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0xb6): relocation truncated to fit: R_X86_64_PC32 against symbol `low' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0xcd): relocation truncated to fit: R_X86_64_PC32 against symbol `low' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0xe5): relocation truncated to fit: R_X86_64_PC32 against symbol `dfn' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0xf1): relocation truncated to fit: R_X86_64_PC32 against symbol `top' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0xfa): relocation truncated to fit: R_X86_64_PC32 against symbol `top' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0x100): relocation truncated to fit: R_X86_64_PC32 against symbol `top' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0x112): relocation truncated to fit: R_X86_64_PC32 against symbol `sta' defined in .bss section in /tmp/cczN2fu3.o
a.cc:(.text+0x121): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status