Submission #12016925

---

Source Code Expand

//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stack>
#define ll long long
#define inf 20021225
#define mid (l+r>>1)
#define M 1000100
#define N 400010
using namespace std;
int read()
{
	int s=0,t=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')	t=-1; ch=getchar();}
	while(ch>='0' && ch<='9')	s=s*10+ch-'0',ch=getchar();
	return s*t;
}
struct node{int x,y,id;}a[M],b[M];
struct edge{int to,lt;}e[M];
int poi,ls[N],rs[N],in[N],cnt,n,tot;
void add(int x,int y){e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;}
void build(int &x,int l,int r,int tag)
{
	if(l==r)	return void(x=tag?a[l].id+n:b[l].id); if(!x) x=++poi;
	build(ls[x],l,mid,tag),build(rs[x],mid+1,r,tag); add(x,ls[x]),add(x,rs[x]);
}
void link(int x,int l,int r,int LL,int RR,int fr)
{
	if(LL>RR)	return;
	if(LL<=l&&RR>=r)	return void(add(fr,x));
	if(LL<=mid)	link(ls[x],l,mid,LL,RR,fr);
	if(RR>mid)	link(rs[x],mid+1,r,LL,RR,fr);
}
stack<int> stk;
int dfn[N],low[N],tms,col[N],cl; bool is[N];
void tarjan(int x)
{
	stk.push(x); dfn[x]=low[x]=++tms; is[x]=1;
	for(int i=in[x];i;i=e[i].lt)
	{
		int y=e[i].to;
		if(!dfn[y])	tarjan(y),low[x]=min(low[x],low[y]);
		else if(is[y])	low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{
		int w=0; cl++;
		do
		{
			w=stk.top(); stk.pop(); col[w]=cl; is[w]=0;
		}while(w!=x);
	}
}
int rem[N],rem_cnt,rtx,rty;
bool check(int val)
{
	int lx,rx;
	for(int i=1;i<=poi;i++)	in[i]=rem[i]; cnt=rem_cnt;
	lx=1,rx=1;
	for(int i=1;i<=n;i++)
	{
		while(lx<i&&a[i].x-a[lx].x>=val)	lx++;
		while(rx<=n&&a[rx].x-a[i].x<val)	rx++;
		link(rtx,1,n,lx,i-1,a[i].id),link(rtx,1,n,i+1,rx-1,a[i].id);
	}
	lx=1,rx=1;
	for(int i=1;i<=n;i++)
	{
		while(lx<=n&&a[i].x-b[lx].y>=val)	lx++;
		while(rx<=n&&b[rx].y-a[i].x<val)	rx++;
		link(rty,1,n,lx,rx-1,a[i].id);
	}
	lx=1,rx=1;
	for(int i=1;i<=n;i++)
	{
		while(lx<=n&&b[i].y-a[lx].x>=val)	lx++;
		while(rx<=n&&a[rx].x-b[i].y<val)	rx++;
		link(rtx,1,n,lx,rx-1,b[i].id+n);
	}
	lx=1,rx=1;
	for(int i=1;i<=n;i++)
	{
		while(lx<i&&b[i].y-b[lx].y>=val)	lx++;
		while(rx<=n&&b[rx].y-b[i].y<val)	rx++;
		link(rty,1,n,lx,i-1,b[i].id+n),link(rty,1,n,i+1,rx-1,b[i].id+n);
	}
	
	while(!stk.empty())	stk.pop(); tms=0;
	for(int i=1;i<=poi;i++)	dfn[i]=low[i]=is[i]=col[i]=0;
	for(int i=1;i<=poi;i++)	if(!dfn[i])	tarjan(i);
	for(int i=1;i<=n;i++)	if(col[i]==col[i+n])	return 0;
	return 1;
}
void get()
{
	int l=0,r=1e9,ans=0;
	while(l<=r)
	{
		int val=l+r>>1;
		if(check(val))	ans=val,l=val+1;
		else	r=val-1;
	}
	printf("%d\n",ans);
}
bool cmpx(node x,node y){return x.x<y.x;}
bool cmpy(node x,node y){return x.y<y.y;}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)	a[i].x=b[i].x=read(),a[i].y=b[i].y=read(),a[i].id=b[i].id=i; poi=2*n;
	sort(a+1,a+n+1,cmpx); sort(b+1,b+n+1,cmpy);
	build(rtx,1,n,1); build(rty,1,n,0);
	for(int i=1;i<=poi;i++)	rem[i]=in[i];
	rem_cnt=cnt; get();
	return 0;
}

Submission Info

Judge Result