【-8】arc 069F-Flags[2-SAT]

Problem Statement

Snuke loves flags.

Snuke is placing $N$ flags on a line.

The $i$-th flag can be placed at either coordinate $x_i$ or coordinate $y_i$.

Snuke thinks that the flags look nicer when the smallest distance between two of them, $d$, is larger. Find the maximum possible value of $d$.

Constraints

  • $2≤N≤10^4$
  • $1≤x_i $ , $ y_i≤10^9$
  • $x_i$ and $y_i$ are integers.

Input

The input is given from Standard Input in the following format:

1
2
3
4
N
X1 Y1
:
Xn Yn

Output

Print the answer.

Sample Input 1

1
2
3
4
3
1 3
2 5
1 9

Sample Output 1

1
4

The optimal solution is to place the first flag at coordinate 1, the second flag at coordinate 5 and the third flag at coordinate 9. The smallest distance between two of the flags is 4 in this case.

Sample Input 2

1
2
3
4
5
6
5
2 2
2 2
2 2
2 2
2 2

Sample Output 2

1
0

There can be more than one flag at the same position.

Sample Input 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
22
93 6440
78 6647
862 11
8306 9689
798 99
801 521
188 206
6079 971
4559 209
50 94
92 6270
5403 560
803 83
1855 99
42 504
75 484
629 11
92 122
3359 37
28 16
648 14
11 269

Sample Output 3

1
17

题解

先二分答案,然后就是2-SAT判定问题(不能有一对点在同一个强连通分量)

偷懒,没用什么线段树优化加边,(毕竟数据水),往后连9条边就好,然后瞎搞一下

跑得还很快
关于2-SAT http://blog.csdn.net/moguxiaozhe/article/details/49047085

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s^'0');
s=getchar();
}
return k*base;
}
const int maxn=2e4+10;
const int maxm=5e5+10;
int n,X,Y,m,l,r,ans;
struct node
{
int id,p,oth;
} a[maxn];
int Map[maxn];
int dfs_time,low[maxn],dfn[maxn],scc[maxn];
int to[maxm],ne[maxm],id,po[maxn],sccid;
stack<int> S;
bool cmp(node aa,node bb)
{
if (aa.p==bb.p) return aa.id<bb.id;
return aa.p<bb.p;
}
inline int qmax(int x,int y)
{
return x>y?x:y;
}
inline int qmin(int x,int y)
{
return x<y?x:y;
}
bool flag;
void tarjan(int x)
{
S.push(x);
dfn[x]=low[x]=++dfs_time;
for (int i=po[x];i;i=ne[i])
{
if (dfn[to[i]]==0)
{
tarjan(to[i]);
if (!flag) return;
low[x]=qmin(low[x],low[to[i]]);
} else
if (scc[to[i]]==0)
{
low[x]=qmin(low[x],dfn[to[i]]);
}
}
if (dfn[x]==low[x])
{
++sccid;
while (!S.empty())
{
scc[S.top()]=sccid;
if (scc[a[S.top()].oth]==sccid)
{
flag=false;
return;
}
if (S.top()==x) {S.pop();break;}
S.pop();
}
}
}
inline void add(int x,int y)
{
id++;to[id]=y;ne[id]=po[x];po[x]=id;
}
bool check(int x)
{
id=0;sccid=0;
dfs_time=0;
memset(po,0,sizeof(po));
memset(low,0,sizeof(low));
memset(scc,0,sizeof(scc));
memset(dfn,0,sizeof(dfn));
for (int i=1;i<m;i++)
{
int last=min(m,i+9);
for (int j=i+1;j<=last;j++)
{
if (a[j].p-a[i].p<x)//连边(其实我的会连出自环,然而不影响,可以判掉)
{
add(i,a[j].oth);
add(j,a[i].oth);
} else break;
}
}
flag=true;
tarjan(1);
for (int i=1;i<=m;i++)
{
if (!dfn[i]) tarjan(i);
if (flag==false) return false;//不可行
}
return true;
}
int main()
{
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
n=read();
for (int i=1;i<=n;i++)
{
X=read();Y=read();
if (X>Y) swap(X,Y);
a[i].id=i, a[i].p=X, a[i].oth=i+n;
a[i+n].id=i+n,a[i+n].p=Y,a[i+n].oth=i;
}
m=n+n;
r=qmax(abs(a[n+1].p-a[2].p),abs(a[n+2].p-a[1].p));
r=qmax(r,qmax(abs(a[2].p-a[1].p),abs(a[n+2].p-a[n+1].p)));//瞎搞一个上界
sort(a+1,a+n+1,cmp);
l=a[2].p-a[1].p;
for (int i=3;i<=n;i++) l=min(l,a[i].p-a[i-1].p);//强选x,搞一个下界

sort(a+1,a+m+1,cmp);
for (int i=1;i<=m;i++) Map[a[i].id]=i;
for (int i=1;i<=m;i++) a[i].oth=Map[a[i].oth];
while (l<=r)
{
int mid=(l+r)>>1;
if (check(mid)) {ans=max(ans,mid);l=mid+1;} else r=mid-1;
}
printf("%d\n",ans);
return 0;
}