蓝书325页的基础题
二分+2-sat
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = + ; struct TwoSAT{
int n;
vector<int> G[maxn];
bool mark[maxn];
int c, s[maxn];///c是表示目前dfs到的个数和已经被标记的集合s
bool dfs(int x){
if (mark[x ^ ]) return false;
if (mark[x]) return true;
mark[x] = true;
s[c++] = x;
for (int i = ; i < G[x].size(); i++)
if (!dfs(G[x][i])) return false;
return true;
} void init(int n){
this->n = n;
for (int i = ; i < * n; i++) G[i].clear();
memset(mark, , sizeof(mark));
} void add_edge(int x, int xval, int y, int yval){
x = x * + xval, y = y * + yval;
G[x ^ ].push_back(y);
G[y ^ ].push_back(x);
} bool solve(){
for (int i = ; i < * n; i += ){
if (!mark[i] && !mark[i + ]){
c = ;
if (!dfs(i)){
while (c) mark[s[--c]] = false;
if (!dfs(i + )) return false;
}
}
}
return true;
}
}; TwoSAT sat;
int n;
int E[maxn], L[maxn];
int ti[maxn][]; bool test(int p){
sat.init(n);
for (int i = ; i < n; i++){
for (int x = ; x < ; x++){
for (int j = i + ; j < n; j++){
for (int y = ; y < ; y++){
if (abs(ti[i][x] - ti[j][y]) < p){
///那就说明不成立，因此要建立成立的边
sat.add_edge(i, x ^ , j, y ^ );
}
}
}
}
}
return sat.solve();
} int main(){
while (scanf("%d", &n) == ){
int lb = , rb = ;
for (int i = ; i < n; i++){
scanf("%d%d", E + i, L + i);
ti[i][] = E[i], ti[i][] = L[i];
rb = max(rb, max(E[i], L[i]));
}
rb++;
while (lb < rb - ){
int mid = (lb + rb) / ;
if (test(mid)) lb = mid;
else rb = mid;
}
printf("%d\n",lb);
}
return ;
}