use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;
fn main(){
let cin = stdin();
let cin = cin.lock();
let mut sc = Scanner::new(cin);
while let Some(n) = sc.read1() {
let mut zs = vec![];
for i in 0..n {
let x: i64 = sc.read();
zs.push((x, i));
let y: i64 = sc.read();
zs.push((y, i));
}
zs.sort();
let zs = zs;
let mut n2 = 1;
while n2 < 2 * n { n2 <<= 1; }
// perform binary search
let mut lo = -1;
let mut hi = 1_000_000_000;
while hi - lo > 1 {
let d = (lo + hi) / 2;
// make 2-SAT instance
let mut vg = vec![vec![]; 4 * n2];
let neg = 2 * n2;
// exactly one flag must be chosen for each (xi, yi)
let mut pairs = vec![vec![]; n];
for (j, &(_, i)) in zs.iter().enumerate() {
pairs[i].push(j);
}
for pair in pairs {
assert_eq!(pair.len(), 2);
or_clause(&mut vg, n2 + pair[0], n2 + pair[1]);
or_clause(&mut vg, neg + n2 + pair[0], neg + n2 + pair[1]);
}
// implication on parent nodes
for i in 2..(2 * n2) {
or_clause(&mut vg, neg + i, i / 2);
}
// distance condition
for i in 0..(2 * n) {
// min j s.t., |z[j] - z[i]| <= d
let mut lo = -1;
let mut hi = i as i32;
while hi - lo > 1 {
let mid = (lo + hi) / 2;
if (zs[mid as usize].0 - zs[i].0).abs() <= d {
hi = mid;
} else {
lo = mid;
}
}
cover(&mut vg, i, hi as usize, i);
// max j s.t., |z[j] - z[i]| <= d
let mut lo = i;
let mut hi = 2 * n;
while hi - lo > 1 {
let mid = (lo + hi) / 2;
if (zs[mid].0 - zs[i].0).abs() <= d {
lo = mid;
} else {
hi = mid;
}
}
cover(&mut vg, i, i + 1, lo + 1);
}
// determine if the 2-SAT instance is feasible
let mut comp = vec![];
let _ = strongly_connected_components(&mut vg, &mut comp);
let mut feasible = true;
for i in 0..(2 * n2) {
if comp[i] == comp[neg + i] {
feasible = false;
}
}
if feasible {
lo = d;
} else {
hi = d;
}
}
println!("{}", hi);
}
}
fn cover(vg: &mut Vec<Vec<usize>>, i: usize, lo: usize, hi: usize) {
fn traverse(node_idx: usize,
node_lp: usize,
node_rp: usize,
lo: usize,
hi: usize,
i: usize,
vg: &mut Vec<Vec<usize>>) {
if node_rp <= lo || hi <= node_lp {
return;
}
if lo <= node_lp && node_rp <= hi {
let neg = vg.len() / 2;
let n2 = vg.len() / 4;
or_clause(vg, neg + n2 + i, neg + node_idx);
return;
}
let node_mp = (node_lp + node_rp) / 2;
traverse(node_idx * 2 + 0, node_lp, node_mp, lo, hi, i, vg);
traverse(node_idx * 2 + 1, node_mp, node_rp, lo, hi, i, vg);
}
let n2 = vg.len() / 4;
traverse(1, 0, n2, lo, hi, i, vg);
}
fn or_clause(vg: &mut Vec<Vec<usize>>, x: usize, y: usize) {
/// 2-SAT clause: (x or y)
let n = vg.len() / 2;
//print!("clause:");
//if x < n { print!(" {}", x); } else { print!(" ~{}", x - n); }
//if y < n { print!(" {}", y); } else { print!(" ~{}", y - n); }
//println!();
let nx = if x < n { x + n } else { x - n };
let ny = if y < n { y + n } else { y - n };
vg[nx].push(y);
vg[ny].push(x);
}
fn strongly_connected_components(vg: &Vec<Vec<usize>>,
component_id: &mut Vec<usize>) -> usize {
let n = vg.len();
component_id.resize(n, 0);
fn dfs1(vg: &Vec<Vec<usize>>,
idx: usize,
count: &mut usize,
visited: &mut Vec<bool>,
t_order: &mut Vec<usize>) {
if visited[idx] {
return;
}
visited[idx] = true;
for &to in &vg[idx] {
dfs1(vg, to, count, visited, t_order);
}
*count -= 1;
t_order[*count] = idx;
}
let mut count = n;
let mut visited = vec![false; n];
let mut t_order = vec![0; n];
for i in 0..n {
dfs1(vg, i, &mut count, &mut visited, &mut t_order);
}
assert_eq!(count, 0);
// make a new graph with edge directions reversed
let mut visited = vec![false; n];
let mut vg_rev = vec![vec![]; n];
for i in 0..n {
for &to in &vg[i] {
vg_rev[to].push(i);
}
}
fn dfs2(vg_rev: &Vec<Vec<usize>>,
idx: usize,
count: usize,
visited: &mut Vec<bool>,
component_id: &mut Vec<usize>) {
visited[idx] = true;
for &from in &vg_rev[idx] {
if !visited[from] {
dfs2(vg_rev, from, count, visited, component_id);
}
}
component_id[idx] = count;
}
for i in 0..n {
let j = t_order[i];
if !visited[j] {
dfs2(&vg_rev, j, count, &mut visited, component_id);
count += 1;
}
}
return count;
}
//=============================================================================
struct Scanner<'a> {
cin: StdinLock<'a>,
}
impl<'a> Scanner<'a> {
fn new(cin: StdinLock<'a>) -> Scanner<'a> {
Scanner { cin: cin }
}
fn read1<T: FromStr>(&mut self) -> Option<T> {
let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect::<String>();
token.parse::<T>().ok()
}
fn read<T: FromStr>(&mut self) -> T {
self.read1().unwrap()
}
}