“相邻两个着陆时间间隔的最小值应尽量大”很容易让人想到二分答案。
因此我们可以二分这个尽可能大的最小值，然后每次建立一个2-SAT的模型。
即满足相邻的四个时间差绝对值如果小于我们枚举的值就连边。
（现在才发现其实2-SAT并不难写……lrj的代码也很好理解）
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+10;
int n,e[maxn],l[maxn];
vector<int> G[maxn*2];
bool vis[maxn*2];
int S[maxn*2],cnt;
void init(int n)
{
for(int i=0;i<n*2;i++)
G[i].clear();
memset(vis,false,sizeof vis);
}
void addedge(int x,bool vx,int y,bool vy)
{
int tx=x*2+vx,ty=y*2+vy;
G[tx^1].push_back(ty);
G[ty^1].push_back(tx);
}
bool DFS(int u)
{
if(vis[u^1])
return false;
if(vis[u])
return true;
vis[S[cnt++]=u]=true;
for(int i=0,size=G[u].size();i<size;i++)
if(!DFS(G[u][i]))
return false;
return true;
}
bool solve()
{
for(int i=0;i<n*2;i+=2)
if(!vis[i]&&!vis[i+1])
{
cnt=0;
if(!DFS(i))
{
while(cnt>0)
vis[S[--cnt]]=false;
if(!DFS(i+1))
return false;
}
}
return true;
}
bool ok(int M)
{
init(n);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
if(abs(e[i]-e[j])<M)
addedge(i,true,j,true);
if(abs(e[i]-l[j])<M)
addedge(i,true,j,false);
if(abs(l[i]-e[j])<M)
addedge(i,false,j,true);
if(abs(l[i]-l[j])<M)
addedge(i,false,j,false);
}
return solve();
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
int L=0,R=0;
for(int i=0;i<n;i++)
{
scanf("%d%d",&e[i],&l[i]);
R=max(R,max(e[i],l[i]));
}
while(L<R)
{
int M=L+(R-L+1)/2;
if(ok(M))
L=M;
else R=M-1;
}
printf("%d\n",L);
}
return 0;
}
/*
10
44 156
153 182
48 109
160 201
55 186
54 207
55 165
17 58
132 160
87 197
*/