Submission #1793701

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
#define SS 23333333
int n,x[SZ],y[SZ],N=0;
int M=0,fst[SS],vb[SS],nxt[SS];
void ad_de(int a,int b){if(a&&b);else return;
++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}
void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
pii px[SZ],py[SZ];
struct seg_base
{
pii ps[SZ]; int pn=0;
inline void add(pii g) {ps[++pn]=g;}
inline void sor() {sort(ps+1,ps+1+pn);}
virtual void init()=0;
virtual int qry_(int l,int r)=0;
virtual int mg(int l,int r)=0;
int qry(int l,int r,pii s)
{
	int L=lower_bound(ps+1,ps+1+pn,pii(l,0))-ps,
	R=lower_bound(ps+1,ps+1+pn,pii(r,1e9))-ps-1;
	int p=lower_bound(ps+1,ps+1+pn,s)-ps;
	return mg(qry_(L,p-1),qry_(p+1,R));
}
};
struct seg_out:public seg_base
{
int M,ss[SZ];
void init()
{
	M=1; while(M<=pn+2) M<<=1;
	for(int i=1;i<=M+M;++i) ss[i]=++N;
	for(int i=1;i<M;++i)
		ad_de(ss[i+i],ss[i]),ad_de(ss[i+i+1],ss[i]);
	for(int i=1;i<=pn;++i)
		ad_de(ps[i].se,ss[i+M]);
}
int mg(int x,int y)
{
	int s=++N;
	ad_de(x,s); ad_de(y,s);
	return s;
}
int qry_(int l,int r)
{
	if(l>r) return ++N;
	int x=++N;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
	{
		if(~l&1) ad_de(ss[l^1],x);
		if(r&1) ad_de(ss[r^1],x);
	}
	return x;
}
}out;
struct seg_in:public seg_base
{
int M,ss[SZ];
void init()
{
	M=1; while(M<=pn+2) M<<=1;
	for(int i=1;i<=M+M;++i) ss[i]=++N;
	for(int i=1;i<M;++i)
		ad_de(ss[i],ss[i+i]),ad_de(ss[i],ss[i+i+1]);
	for(int i=1;i<=pn;++i)
		ad_de(ss[i+M],ps[i].se);
}
int mg(int x,int y)
{
	int s=++N;
	ad_de(s,x); ad_de(s,y);
	return s;
}
int qry_(int l,int r)
{
	if(l>r) return ++N;
	int x=++N;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
	{
		if(~l&1) ad_de(x,ss[l^1]);
		if(r&1) ad_de(x,ss[r^1]);
	}
	return x;
}
}inf;
int bl[SS],dfn[SS],low[SS],C=0,st[SS],sn=0,Z=0;
bool ins[SS];
void tj(int x)
{
	dfn[x]=low[x]=++C; st[++sn]=x; ins[x]=1;
	for esb(x,e,b)
	{
		if(!dfn[b]) tj(b),low[x]=min(low[x],low[b]);
		else if(ins[b]) low[x]=min(low[x],dfn[b]);
	}
	if(dfn[x]!=low[x]) return;
	++Z; int g=-1;
	while(g!=x) g=st[sn--],ins[g]=0,bl[g]=Z;
}
bool ok(int d)
{
	N=n+n; M=C=Z=0;
	out.init(); inf.init();
	for(int i=1;i<=n;++i)
	{
		ad_de(out.qry(x[i]-d,x[i]+d,pii(x[i],i*2-1)),i*2);
		ad_de(i*2-1,inf.qry(x[i]-d,x[i]+d,pii(x[i],i*2)));
		ad_de(out.qry(y[i]-d,y[i]+d,pii(y[i],i*2)),i*2-1);
		ad_de(i*2,inf.qry(y[i]-d,y[i]+d,pii(y[i],i*2-1)));
	}
	for(int i=1;i<=n+n;++i)
		if(!dfn[i]) tj(i);
	for(int i=1;i<=N;++i) fst[i]=dfn[i]=0;
	for(int i=1;i<=n;++i)
		if(bl[i*2-1]==bl[i*2])
			return 0;
	return 1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d",x+i,y+i),
		px[i]=pii(x[i],i),
		py[i]=pii(y[i],i);
	sort(px+1,px+1+n);
	sort(py+1,py+1+n);
	for(int i=1;i<=n;++i)
		out.add(pii(x[i],i*2-1)),
		out.add(pii(y[i],i*2));
	for(int i=1;i<=n;++i)
		inf.add(pii(x[i],i*2)),
		inf.add(pii(y[i],i*2-1));
	out.sor(); inf.sor();
	int l=-1,r=1e9;
	while(l<r)
	{
		int g=(l+r+1)>>1;
		if(ok(g)) l=g; else r=g-1;
	}
	printf("%d\n",l+1);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:151:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:155:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   py[i]=pii(y[i],i);
                    ^

Judge Result