题目大意：
将 \(N\)个标志放在一条线上，第 \(i\) 个标志可以放置在坐标 \(x_i\) 或坐标 \(y_i\) 上。
\(Snuke\) 认为当他们中的两个之间的最小距离 \(d\) 更大时，标志看起来更好。
找出 \(d\) 的最大可能值。
\(n<=10^4,x_i,y_i<=10^9\)
solution
每个点只有两种选择，同时每个点选择之间会存在不合法，2-SAT 问题
显然，答案具有二分性
二分一个答案，然后确定那些点不能同时选，向它的对立点连边，
如果一个点的两个位置在一个强连通分量中，那么答案就不合法
连边是 \(O(n^2)\) 的，会 T
因为每个点可以是对一个区间连边，所以可以把每个点按照位置排个序，线段树优化建图就好了
code
/*
work by:Ariel_
*/
#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#define int long long
#define clear(x) memset(x, 0, sizeof(x))
#define op(x) ((x) <= n ? (x) + n : (x) - n)
#define lson rt << 1
#define rson rt << 1 | 1
using namespace std;
const int N = 3e6 + 5, K = 1e4 + 5;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < ‘0‘ || c > ‘9‘){if (c == ‘-‘) f = -1;c = getchar();}
while(c >= ‘0‘ && c <= ‘9‘) {x = x * 10 + c - ‘0‘;c = getchar();}
return x * f;
}
int n, id[N], ans, cnt;
struct FLAGS{
int pos, id;
bool operator<(const FLAGS& f) const { return pos < f.pos; }
FLAGS(int pos = 0):pos(pos){};
}flg[N];
struct edge{int v, nxt;}e[N];
bool cmp(FLAGS x, FLAGS y){return x.pos < y.pos;}
int head[N], E;
void add_edge(int u, int v) {
e[++E] = (edge) {v, head[u]};
head[u] = E;
}
namespace Seg{
void build(int rt, int l, int r) {
id[rt] = ++cnt;
if (l == r) {
add_edge(id[rt], op(flg[l].id));
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
add_edge(id[rt], id[lson]), add_edge(id[rt], id[rson]);
}
void modify(int rt, int l, int r, int L, int R, int v) {
if (L > R) return ;
int mid = (l + r) >> 1;
if (l == L && r == R) add_edge(v, id[rt]);
else if (R <= mid) modify(lson, l, mid, L, R, v);
else if (L > mid) modify(rson, mid + 1, r, L, R, v);
else modify(lson, l, mid, L, mid, v), modify(rson, mid + 1, r, mid + 1, R, v);
}
}
using namespace Seg;
int vis[N], dfn[N], low[N], tot, sc, scc[N];
stack<int> s;
void tarjan(int x) {
low[x] = dfn[x] = ++tot;
s.push(x), vis[x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(vis[v]) low[x] = min(dfn[v], low[x]);
}
int k;
if (low[x] == dfn[x]) {
sc++;
do{
k = s.top(), s.pop();
scc[k] = sc, vis[k] = 0;
}while(k != x);
}
}
bool check(int v) {
clear(head), clear(low), clear(dfn), clear(e), clear(vis), clear(scc);
E = tot = cnt = 0;
build(1, 1, cnt = 2 * n);
int l, r;
for (int i = 1; i <= 2 * n; i++) {
l = upper_bound(flg + 1, flg + 2 * n + 1, FLAGS(flg[i].pos - v)) - flg;
r = upper_bound(flg + 1, flg + 2 * n + 1, FLAGS(flg[i].pos + v - 1)) - flg - 1;
modify(1, 1, 2 * n, l, i - 1, flg[i].id), modify(1, 1, 2 * n, i + 1, r, flg[i].id);
}
for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) if(scc[i] == scc[i + n]) return 0;
return 1;
}
signed main(){
n = read();
for (int i = 1; i <= n; i++) {
flg[i].pos = read(), flg[i + n].pos = read();
flg[i].id = i, flg[i + n].id = i + n;
}
sort(flg + 1, flg + 2 * n + 1, cmp);
int l = 0, r = flg[2 * n].pos - flg[1].pos + 1;
while(l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
printf("%lld", ans);
puts("");
return 0;
}