D45 2-SAT+二分 UVA1146 Now or later

// 2-SAT+二分 O(n*n*logt)
#include<bits/stdc++.h>
using namespace std;

const int N=4010;
int n,t[N][2];
vector<int> v[N]; //邻接表
int dfn[N],low[N],scc[N],stk[N],tim,top,cnt;

void tarjan(int x){
  dfn[x]=low[x]=++tim;
  stk[++top]=x;
  for(int y:v[x]){
    if(!dfn[y]){ //若y尚未访问
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if(!scc[y]) //若y已访问且未处理
      low[x]=min(low[x],dfn[y]);
  }
  
  if(low[x]==dfn[x]){ //若x是SCC的根
    ++cnt;
    for(int y=-1;y!=x;)
      scc[y=stk[top--]]=cnt;
  }
}
bool check(int mid){
  for(int i=1;i<=2*n;++i) v[i].clear();
  memset(dfn,0,sizeof dfn);
  memset(low,0,sizeof low);
  memset(scc,0,sizeof scc);
  tim=top=cnt=0;
  
  for(int i=1;i<=n;++i){ //建图: 注意逆否与对称
    for(int j=i+1;j<=n;++j){
      if(abs(t[i][0]-t[j][0])<mid) //i,j都早不行
        v[i].push_back(j+n), //i早→j晚
        v[j].push_back(i+n); //j早→i晚
      if(abs(t[i][0]-t[j][1])<mid) //i早,j晚不行
        v[i].push_back(j),    //i早→j早
        v[j+n].push_back(i+n);//j晚→i晚       
      if(abs(t[i][1]-t[j][0])<mid) //i晚,j早不行
        v[i+n].push_back(j+n),//i晚→j晚
        v[j].push_back(i);    //j早→i早
      if(abs(t[i][1]-t[j][1])<mid) //i,j都晚不行
        v[i+n].push_back(j), //i晚→j早
        v[j+n].push_back(i); //j晚→i早      
    }
  }
  
  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;
}
int main(){
  while(scanf("%d",&n)!=EOF){
    for(int i=1;i<=n;++i)
      scanf("%d%d",&t[i][0],&t[i][1]);
      
    int l=0,r=1e7+1,mid; //二分时间
    while(l+1<r){ 
      mid=(l+r)>>1;
      check(mid)?l=mid:r=mid;
    }
    printf("%d\n",l);   
  }
}

// 2-SAT+线段树优化+二分 O(nlognlogx)
#include<bits/stdc++.h>
using namespace std;

#define mid ((l+r)>>1)
#define ls (u<<1)
#define rs (u<<1|1)

const int N=4010,M=N<<2;
vector<int> v[M]; //邻接表
int dfn[M],low[M],stk[M],scc[M],tim,top,sc;
int n,tot,id[M];
struct F{
  int x,id; //坐标,编号
  F(int x=0):x(x){}
  bool operator<(const F& b)const{return x<b.x;}
}f[N]; //旗子

void build(int u,int l,int r){
  id[u]=++tot; //节点编号
  if(l==r){
    int x=f[l].id;
    v[id[u]].push_back(x<=n?x+n:x-n); //叶子向反点连边
    return;
  }
  build(ls,l,mid);
  build(rs,mid+1,r);
  v[id[u]].push_back(id[ls]);
  v[id[u]].push_back(id[rs]); //父向子连边
}
void link(int u,int l,int r,int x,int y,int p){
  if(x>r||y<l) return;
  if(x<=l&&r<=y){
    v[p].push_back(id[u]); //p点向区间id[u]连边
    return;
  }
  link(ls,l,mid,x,y,p),
  link(rs,mid+1,r,x,y,p);
}
#undef mid

void tarjan(int x){
  dfn[x]=low[x]=++tim;
  stk[++top]=x;
  for(int y:v[x]){
    if(!dfn[y]){ //若y尚未访问
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if(!scc[y]) //若y已访问且未处理
      low[x]=min(low[x],dfn[y]);
  }
  if(low[x]==dfn[x]){ //若x是SCC的根
    ++sc;
    for(int y=-1;y!=x;)
      scc[y=stk[top--]]=sc;
  }
}
bool check(int mid){
  for(int i=1;i<=8*n;++i) v[i].clear();
  memset(dfn,0,sizeof(dfn));
  memset(low,0,sizeof(low));
  memset(scc,0,sizeof(scc));
  memset(stk,0,sizeof(stk));
  tim=top=sc=0;
  
  build(1,1,tot=2*n);
  for(int i=1,x,y;i<=2*n;i++){
    x=upper_bound(f+1,f+1+2*n,F(f[i].x-mid))-f;
    y=lower_bound(f+1,f+1+2*n,F(f[i].x+mid))-f-1;
    link(1,1,2*n,x,i-1,f[i].id); //x是距离<mid的左下标
    link(1,1,2*n,i+1,y,f[i].id); //y是距离<mid的右下标
  }
  
  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;
}
int main(){
  while(scanf("%d",&n)!=EOF){
    for(int i=1;i<=n;i++){
      scanf("%d%d",&f[i].x,&f[i+n].x);
      f[i].id=i,f[i+n].id=i+n; //点的编号
    }
    sort(f+1,f+n*2+1); //按x排序
    int l=0,r=1e7+1,mid;
    while(l+1<r){ //二分距离
      mid=(l+r)>>1;
      check(mid)?l=mid:r=mid;
    }
    printf("%d\n",l);
  }
}