原题链接
显然,答案具有单调性.所以珂以考虑二分
假设目前二分的答案为\(\text{d}\).
现在题目转化为:有\(2N\)个坐标,其中有一些不能被Flags同时占据,问是否有一种Flags占据坐标的方法.
在所有珂能的坐标中,两个坐标\(x_1, x_2\)不能同时被Flags占据的充要条件是\(|x_1-x_2|\ge d\)且\(\text{belong}_{x_1}!=\text{belong}_{x2}\)
这珂以用\(\text{2-sat}\)解决.
然后还有一个问题,就是珂能有非常多组坐标不能同时被Flags占据,如果直接在\(\text{2-sat}\)中建边就会爆掉.
先把所有的坐标排序,放置在数组A中.
考虑对于每一个\(x_1\),若\(x_2\)和\(x_1\)不能同时被Flags占据,那么\(x_2\)在数组A中的位置是以一个区间和零散的坐标的形式呈现.
所以我们珂以线段树优化建图.
时间复杂度\(O(n\log n\log \text{1e9})\) 然而窝人傻常数太大跑得极慢
贴一下代码：
// by H~$~C
#include <bits/stdc++.h>
using namespace std;
static const int Maxn = 20005;
int n;
int x[Maxn], y[Maxn];
vector<pair<int, int> > pos;
namespace two_sat {
int n;
vector<vector<int> > g;
vector<int> dfn, scc, low;
vector<bool> instk;
int scc_size, indx;
stack<int> stk;
void tarjan(int u) {
dfn[u] = low[u] = ++indx;
stk.push(u);
instk[u] = true;
for (int &v: g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scc_size++;
do {
int v = stk.top(); stk.pop();
scc[v] = scc_size;
instk[v] = false;
if (v == u) break;
} while (1);
}
}
inline int inv(int x) { return x ^ 1; }
inline void clear() {
n = 0, g.clear();
while (!stk.empty()) stk.pop();
scc_size = indx = 0;
instk.clear();
}
inline int newnode() {
g.push_back(vector<int>());
g.push_back(vector<int>());
return 2 * n++;
}
inline void init(int x) {
clear();
while (n < x) newnode();
}
inline void imply(int a, int b) {
g[a].push_back(b);
g[inv(b)].push_back(inv(a));
}
bool solve() {
dfn.assign(n * 2, 0);
low.assign(n * 2, 0);
scc.assign(n * 2, 0);
instk.assign(n * 2, false);
scc_size = indx = 0;
for (int i = 0; i < n * 2; ++i) {
if (!dfn[i]) {
tarjan(i);
}
}
for (int i = 0; i < n; ++i) {
if (scc[2 * i] == scc[2 * i + 1])
return false;
}
return true;
}
}
#define ls (p * 2 + 1)
#define rs (p * 2 + 2)
#define mid (l + r >> 1)
int tr[Maxn << 2];
void build(int p, int l, int r) {
tr[p] = two_sat::newnode();
if (l == r) {
two_sat::imply(tr[p], two_sat::inv(pos[l].second));
return ;
}
build(ls, l, mid);
build(rs, mid + 1, r);
two_sat::imply(tr[p], tr[ls]);
two_sat::imply(tr[p], tr[rs]);
}
void link_edge(int p, int l, int r, int L, int R, int id) {
if (L > r || l > R) return ;
if (L <= l && r <= R) {
two_sat::imply(id, tr[p]);
return ;
}
link_edge(ls, l, mid, L, R, id);
link_edge(rs, mid + 1, r, L, R, id);
}
#undef ls
#undef rs
#undef mid
bool check(int d) {
two_sat::init(n);
build(0, 0, n * 2 - 1);
for (int i = 0; i < n * 2; ++i) {
int st = lower_bound(pos.begin(), pos.end(), make_pair(pos[i].first - d + 1, 0)) - pos.begin();
int ed = lower_bound(pos.begin(), pos.end(), make_pair(pos[i].first + d, 0)) - pos.begin();
if (i > st) link_edge(0, 0, n * 2 - 1, st, i - 1, pos[i].second);
if (i < ed - 1) link_edge(0, 0, n * 2 - 1, i + 1, ed - 1, pos[i].second);
}
return two_sat::solve();
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d", x + i, y + i);
pos.push_back({x[i], i * 2});
pos.push_back({y[i], i * 2 + 1});
}
sort(pos.begin(), pos.end());
int l = 0, r = 1000000000, ans = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
printf("%d\n", ans);
return 0;
}