Language: C++

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=last[a];i;i=next[i])
using namespace std;

int read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

const int N=1e6+5,inf=1e9;

struct pty{int x,y,id;}a[N],b[N];
bool cmpx(pty a,pty b) {return a.x<b.x;}
bool cmpy(pty a,pty b) {return a.y<b.y;}

int last[N],now[N],next[N],t[N],l,cnt;
void add(int x,int y) {
	t[++l]=y;next[l]=last[x];last[x]=l;
}

int n,tot;
void init() {
	n=read();tot=2*n;
	fo(i,1,n) {
		a[i].x=read();a[i].y=read();a[i].id=i;
		b[i].x=a[i].x;b[i].y=a[i].y;b[i].id=i;
	}
}

int rootx,rooty,le[N],ri[N];
void build(int &v,int l,int r,int flag) {
	if (l==r) {
		v=(flag==1)?(a[l].id+n):b[l].id;
		return;
	}
	v=++tot;
	int mid=l+r>>1;
	build(le[v],l,mid,flag);
	build(ri[v],mid+1,r,flag);
	add(v,le[v]);add(v,ri[v]);
}

void link(int v,int l,int r,int x,int y,int z) {
	if (x>y) return;
	if (l==x&&r==y) {add(z,v);return;}
	int mid=l+r>>1;
	if (y<=mid) link(le[v],l,mid,x,y,z);
	else if (x>mid) link(ri[v],mid+1,r,x,y,z);
	else link(le[v],l,mid,x,mid,z),link(ri[v],mid+1,r,mid+1,y,z);
}

void prepare() {
	sort(a+1,a+n+1,cmpx);
	build(rootx,1,n,1);
	sort(b+1,b+n+1,cmpy);
	build(rooty,1,n,2);
	fo(i,1,tot) now[i]=last[i];cnt=l;
}

int dfn[N],low[N],stack[N],cl[N],tmp,top,id;
bool vis[N],in[N];
void tarjan(int x) {
	vis[x]=in[x]=1;dfn[x]=low[x]=++tmp;stack[++top]=x;
	rep(i,x)
		if (!vis[t[i]]) {
			tarjan(t[i]);
			low[x]=min(low[x],low[t[i]]);
		} else if (in[t[i]]) low[x]=min(low[x],dfn[t[i]]);
	if (low[x]==dfn[x]) {
		stack[top+1]=0;++id;
		for(;stack[top+1]!=x;top--) {
			in[stack[top]]=0;
			cl[stack[top]]=id;
		}
	}
}

bool check(int mid) {
	int lx,rx;
	fo(i,1,tot) last[i]=now[i];l=cnt;
	lx=1,rx=1;
	fo(i,1,n) {
		while (lx<i&&a[i].x-a[lx].x>=mid) lx++;
		while (rx<=n&&a[rx].x-a[i].x<mid) rx++;
		link(rootx,1,n,lx,i-1,a[i].id);
		link(rootx,1,n,i+1,rx-1,a[i].id);
	}
	// xuan x ban x
	lx=1,rx=1;
	fo(i,1,n) {
		while (lx<=n&&b[i].y-a[lx].x>=mid) lx++;
		while (rx<=n&&a[rx].x-b[i].y<mid) rx++;
		link(rootx,1,n,lx,rx-1,b[i].id+n);
	}
	// xuan y ban x
	lx=1,rx=1;
	fo(i,1,n) {
		while (lx<=n&&a[i].x-b[lx].y>=mid) lx++;
		while (rx<=n&&b[rx].y-a[i].x<mid) rx++;
		link(rooty,1,n,lx,rx-1,a[i].id);
	}
	// xuan x ban y
	lx=1,rx=1;
	fo(i,1,n) {
		while (lx<i&&b[i].y-b[lx].y>=mid) lx++;
		while (rx<=n&&b[rx].y-b[i].y<mid) rx++;
		link(rooty,1,n,lx,i-1,b[i].id+n);
		link(rooty,1,n,i+1,rx-1,b[i].id+n);
	}
	// xuan y ban y
	
	tmp=top=id=0;
	fo(i,1,tot) vis[i]=cl[i]=dfn[i]=low[i]=0;
	fo(i,1,tot) if (!vis[i]) tarjan(i);
	fo(i,1,n) if (cl[i]==cl[i+n]) return 0;
	return 1;
}

void solve() {
	int l=0,r=inf;
	while (l<r) {
		int mid=l+r>>1;
		if (check(mid)) l=mid+1;
		else r=mid;
	}
	printf("%d\n",l-1);
}

int main() {
	init();
	prepare();
	solve();
	return 0;
}

Compiler output:
a.cc: In function 'void add(int, int)':
a.cc:25:18: error: reference to 'next' is ambiguous
   25 |         t[++l]=y;next[l]=last[x];last[x]=l;
      |                  ^~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:66,
                 from /usr/include/c++/14/algorithm:60,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:23:20: note:                 'int next [1000005]'
   23 | int last[N],now[N],next[N],t[N],l,cnt;
      |                    ^~~~
a.cc: In function 'void tarjan(int)':
a.cc:6:40: error: reference to 'next' is ambiguous
    6 | #define rep(i,a) for(int i=last[a];i;i=next[i])
      |                                        ^~~~
a.cc:71:9: note: in expansion of macro 'rep'
   71 |         rep(i,x)
      |         ^~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:23:20: note:                 'int next [1000005]'
   23 | int last[N],now[N],next[N],t[N],l,cnt;
      |                    ^~~~