rt 代码十分友善

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int MAXN = 10005;
const int MAXNd = 100005;
const int MAXEg = 1000005;
struct edge {int from, to, nxt;} edges[MAXEg]; int head[MAXNd], tot;
int n;
void add(int u, int v) {edges[++tot].to = v; edges[tot].from = u; edges[tot].nxt = head[u]; head[u] = tot;}
void clear() {for (int i = 1; i < MAXNd; i++) head[i] = 0; tot = 0;}
void print() {for (int i = 1; i <= tot; i++) printf("%d %d\n", edges[i].from, edges[i].to);}
namespace scc {
	int sccid[MAXNd], dfn[MAXNd], low[MAXNd], tim, idtot; stack<int> stk; bool instack[MAXNd];
	void dfs(int u) {
		stk.push(u); dfn[u] = low[u] = ++tim; instack[u] = 1;
		for (int i = head[u]; i; i = edges[i].nxt) {
			if (dfn[edges[i].to] == 0) dfs(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
			else if (instack[edges[i].to]) low[u] = min(low[u], dfn[edges[i].to]);
		}
		if (dfn[u] == low[u]) {++idtot; int y; do {
			y = stk.top(); stk.pop(); instack[y] = 0; sccid[y] = idtot;
		} while (y != u); }
	}
	void main() {
		tim = 0; idtot = 0;
		for (int i = 1; i < MAXNd; i++) dfn[i] = low[i] = 0;
		for (int i = 1; i < MAXNd; i++) if (dfn[i] == 0) dfs(i);
	}
}
pair<int, int*> cors[MAXN << 1]; int corsn[MAXN << 1]; pair<int, int> chs[MAXN]; int ano[MAXN];
namespace sgt {
	int build(int rt, int l, int r) {
		if (l == r) return add(rt + (n << 1), ano[l]), rt + (n << 1); int mid = (l + r) >> 1; add(rt + (n << 1), build(rt << 1, l, mid)); add(rt + (n << 1), build(rt << 1 | 1, mid + 1, r)); return rt + (n << 1);
	}
	// int getid(int rt, int l, int r, int u) {
	// 	if (l == r) return rt + (n << 1); int mid = (l + r) >> 1; if (u <= mid) return getid(rt << 1, l, mid, u); else return getid(rt << 1 | 1, mid + 1, r, u);
	// }
	void conn(int rt, int l, int r, int u, int v, int w) {
		// printf("%d %d %d %d %d %d\n", rt, l, r, u, v, w);
		if (u <= l && r <= v) return add(w, rt + (n << 1)), void(); int mid = (l + r) >> 1; if (u <= mid) conn(rt << 1, l, mid, u, v, w); if (v > mid) conn(rt << 1 | 1, mid + 1, r, u, v, w);
	}
}
bool check(int mid) {
	clear(); sgt::build(1, 1, n << 1); for (int i = 1; i <= n << 1; i++) {
		int ll = lower_bound(corsn + 1, corsn + (n << 1) + 1, corsn[i] - mid) - corsn;
		int rr = upper_bound(corsn + 1, corsn + (n << 1) + 1, corsn[i] + mid) - corsn - 1;
		// if (ll > 1) sgt::conn(1, 1, n << 1, 1, ll - 1, i);
		// if (rr < n << 1) sgt::conn(1, 1, n << 1, rr + 1, n, i);
		// printf("%d %d : %d %d(%d)\n", ll, rr, corsn[ll], corsn[rr], corsn[i]);
		// sgt::conn(1, 1, n << 1, ll, rr, i);
		if (ll < i) sgt::conn(1, 1, n << 1, ll, i - 1, i);
		if (rr > i) sgt::conn(1, 1, n << 1, i + 1, rr, i);
	}
	scc::main(); for (int i = 1; i <= n; i++) {
		if (scc::sccid[chs[i].first] == scc::sccid[chs[i].second]) return 0;
	}
	return 1;
}
namespace binsearch {
	int main() {
		int l = -1, r = 1145141919;
		while (l + 1 < r) {
			// printf("%d %d\n", l, r);
			int mid = (l + r) >> 1; if (check(mid)) l = mid; else r = mid;
		}
		return r;
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d %d", &chs[i].first, &chs[i].second), cors[(i << 1) - 1] = make_pair(chs[i].first, &chs[i].first), cors[i << 1] = make_pair(chs[i].second, &chs[i].second);
	sort(cors + 1, cors + (n << 1) + 1);
	for (int i = 1; i <= n << 1; i++) *(cors[i].second) = i, corsn[i] = cors[i].first/*, printf("%d\n", i)*/;
	for (int i = 1; i <= n; i++) ano[chs[i].first] = chs[i].second, ano[chs[i].second] = chs[i].first;
	// printf("%d", check(4));
	// print();
	// for (int i = 1; i <= 19; i++) printf("%d %d\n", i, scc::sccid[i]);
	printf("%d\n", binsearch::main());
	return 0;
}