Submission #1662483

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100100,M=2002000;
int i,j,k,n,m,ch,En,tm,nm,dn;
int A[N],B[N],b[N],d[N],z[N],p[N],pp[N],h[N];
struct cc {
	int x,y;
	bool operator < (const cc &n) const {
		return x<n.x;
	}
} P[N],Ls[N];
struct edge { int s,n;} E[M];
void R(int &x) {
	x=0;ch=getchar();
	while (ch<'0' || '9'<ch) ch=getchar();
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
}
int find_upper(int x) {
	int l=1,r=m,mid;
	if (Ls[r].x<x) return m+1;
	while (l<r) {
		mid=(l+r-1)>>1;
		if (Ls[mid].x<x) l=mid+1;
		else r=mid;
	}
	return l;
}
int find_lower(int x) {
	int l=1,r=m,mid;
	if (Ls[l].x>x) return 0;
	while (l<r) {
		mid=(l+r+1)>>1;
		if (Ls[mid].x>x) r=mid-1;
		else l=mid;
	}
	return l;
}
void E_add(int x,int y) {
	E[++En].s=y;E[En].n=h[x];h[x]=En;
}
void T_build(int L,int R,int k) {
	if (L==R) {
		if (Ls[L].y<=n) pp[k]=n+Ls[L].y;
		else pp[k]=Ls[L].y-n;
		return;
	}
	int mid=(L+R)>>1;
	T_build(L,mid,k<<1);
	T_build(mid+1,R,k<<1|1);
	pp[k]=m+k;
	E_add(pp[k],pp[k<<1]);
	E_add(pp[k],pp[k<<1|1]);
}
void T_add(int L,int R,int l,int r,int x,int k) {
	if (L==l && R==r) {
		E_add(x,pp[k]);
		return;
	}
	int mid=(L+R)>>1;
	if (r<=mid) T_add(L,mid,l,r,x,k<<1);
	else {
		if (l>mid) T_add(mid+1,R,l,r,x,k<<1|1);
		else T_add(L,mid,l,mid,x,k<<1),T_add(mid+1,R,mid+1,r,x,k<<1|1);
	}
}
void Tj(int x) {
	A[x]=B[x]=++tm;
	d[++dn]=x;z[x]=1;
	for (int k=h[x];k;k=E[k].n) {
		if (!A[E[k].s]) {
			Tj(E[k].s);
			B[x]=min(B[x],B[E[k].s]);
		}
		else if (z[E[k].s]) B[x]=min(B[x],A[E[k].s]);
	}
	if (A[x]==B[x]) {
		int now=0;
		nm++;
		while (now!=x) {
			now=d[dn--];
			b[now]=nm;
			z[now]=0;
		}
	}
}
bool check(int x) {
	memset(h,0,sizeof h);
	memset(b,0,sizeof b);
	memset(A,0,sizeof A);
	memset(z,0,sizeof z);
	dn=tm=nm=En=0;
	T_build(1,m,1);
	int i,j,k;
	for (i=1;i<=n;i++) {
		int l=find_upper(P[i].x-x+1),r=find_lower(P[i].x+x-1);
		if (l<p[i]) T_add(1,m,l,p[i]-1,i,1);
		if (p[i]<r) T_add(1,m,p[i]+1,r,i,1);
		l=find_upper(P[i].y-x+1),r=find_lower(P[i].y+x-1);
		if (l<p[n+i]) T_add(1,m,l,p[n+i]-1,n+i,1);
		if (p[n+i]<r) T_add(1,m,p[n+i]+1,r,n+i,1);
	}
	for (i=1;i<=m+1;i++) if (!A[i]) Tj(i);
	for (i=1;i<=n;i++) if (b[i]==b[n+i]) return 0;
	return 1;
}
int main() {
	R(n);m=n+n;
	for (i=1;i<=n;i++) {
		R(P[i].x),R(P[i].y);
		Ls[i].x=P[i].x;Ls[i].y=i;
		Ls[n+i].x=P[i].y;Ls[n+i].y=n+i;
	}
	sort(Ls+1,Ls+m+1);
	for (i=1;i<=m;i++) p[Ls[i].y]=i;
	int l=0,r=1000000000,mid;
	while (l<r) {
		mid=(l+r+1)>>1;
		if (check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d\n",l);
}

Submission Info

Judge Result