Submission #1201149
Source Code Expand
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
#ifdef DEB
#define dump(x) cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;
namespace std{
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.fr<<','<<a.sc<<')';
return out;
}
}
//const int INF=5e8;
struct SCC{
static const int MAX_N =80000*2;
vector<int> g[MAX_N],rg[MAX_N];
int vis[MAX_N],order[MAX_N],cnt;
int group[MAX_N],gcnt;
void adde(int a,int b){
g[a].pb(b);
rg[b].pb(a);
}
void init(){
REP(i,MAX_N) g[i].clear(),rg[i].clear();
}
void dfs(int v){
vis[v]=1;
REP(i,g[v].size()) if(!vis[g[v][i]]){
dfs(g[v][i]);
}
order[cnt++]=v;
}
void rdfs(int v){
vis[v]=1;
group[v]=gcnt;
REP(i,rg[v].size()) if(!vis[rg[v][i]]){
rdfs(rg[v][i]);
}
}
void scc(int n){
memset(vis,0,sizeof(vis));
cnt=gcnt=0;
REP(i,n) if(!vis[i]){
dfs(i);
}
memset(vis,0,sizeof(vis));
for(int i=n-1;i>=0;--i) if(!vis[order[i]]){
rdfs(order[i]);
++gcnt;
}
}
bool check(int n){
REP(i,n) if(group[i]==group[i+n]) return false;
return true;
}
};
SCC graph;
int n;
struct segtree{
int n,cnt;
int val[80005];
void init(int n_){
n=1;
while(n<n_) n<<=1;
memset(val,-1,sizeof(val));
cnt=(::n)*2;
}
void add(int x,int dst){
x+=n-1;
graph.adde(x+n*2,dst);
while(x>0){
x=(x-1)/2;
graph.adde(x+n*2,dst);
}
}
void link(int a,int b,int i,int l,int r,int src){
if(a<=l && r<=b){
graph.adde(src,i+n*2);
return;
}
if(b<=l || r<=a) return;
int md=(l+r)>>1;
link(a,b,i*2+1,l,md,src);
link(a,b,i*2+2,md,r,src);
}
};
segtree seg;
pi ps[10005];
pi zip[20005];
int zn;
int look(pi x){
return lower_bound(zip,zip+zn,x)-zip;
}
bool check(int d){
zn=0;
--d;
REP(i,n){
zip[zn++]={ps[i].fr,i};
zip[zn++]={ps[i].sc,i};
}
sort(zip,zip+zn);
graph.init();
seg.init(zn);
int vs=seg.n*2;
REP(i,n){
int xlb=look({ps[i].fr-d,-1}),xub=look({ps[i].fr+d+1,-1}),ylb=look({ps[i].sc-d,-1}),yub=look({ps[i].sc+d+1,-1});
int x=look({ps[i].fr,i}),y=look({ps[i].sc,i});
seg.link(xlb,x,0,0,seg.n,i);
seg.link(x+1,xub,0,0,seg.n,i);
seg.link(ylb,y,0,0,seg.n,i+n);
seg.link(y+1,yub,0,0,seg.n,i+n);
seg.add(x,i+n);
seg.add(y,i);
}
graph.scc(vs+n*2);
return graph.check(n);
}
int main(){
cin>>n;
REP(i,n) cin>>ps[i].fr>>ps[i].sc;
int lb=0,ub=1e9+10;
while(ub-lb>1){
int md=(lb+ub)>>1;
if(check(md)) lb=md;
else ub=md;
}
printf("%d\n",lb);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Flags |
User |
hogloid |
Language |
C++14 (GCC 5.4.1) |
Score |
1200 |
Code Size |
3688 Byte |
Status |
AC |
Exec Time |
1114 ms |
Memory |
27008 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
17 ms |
8704 KB |
00_example_02.txt |
AC |
17 ms |
8704 KB |
00_example_03.txt |
AC |
18 ms |
8704 KB |
01.txt |
AC |
37 ms |
9216 KB |
02.txt |
AC |
24 ms |
8960 KB |
03.txt |
AC |
19 ms |
8704 KB |
04.txt |
AC |
19 ms |
8704 KB |
05.txt |
AC |
20 ms |
8832 KB |
06.txt |
AC |
888 ms |
24448 KB |
07.txt |
AC |
949 ms |
24448 KB |
08.txt |
AC |
943 ms |
24448 KB |
09.txt |
AC |
38 ms |
9216 KB |
10.txt |
AC |
24 ms |
8832 KB |
11.txt |
AC |
19 ms |
8704 KB |
12.txt |
AC |
19 ms |
8704 KB |
13.txt |
AC |
20 ms |
8704 KB |
14.txt |
AC |
870 ms |
22016 KB |
15.txt |
AC |
1025 ms |
22016 KB |
16.txt |
AC |
890 ms |
22036 KB |
17.txt |
AC |
38 ms |
9216 KB |
18.txt |
AC |
25 ms |
8832 KB |
19.txt |
AC |
1114 ms |
23808 KB |
20.txt |
AC |
1111 ms |
23808 KB |
21.txt |
AC |
1067 ms |
23808 KB |
22.txt |
AC |
1062 ms |
23936 KB |
23.txt |
AC |
1002 ms |
27008 KB |
24.txt |
AC |
816 ms |
24960 KB |
25.txt |
AC |
805 ms |
25984 KB |
26.txt |
AC |
968 ms |
24064 KB |
27.txt |
AC |
17 ms |
8704 KB |