题目链接：https://vjudge.net/problem/UVALive-3211

题意：每架飞机有早晚起降两种方式，给定n架飞机两种方式的起落时间，为每架飞机安排起落时间（早或

晚），使得所有飞机起降时间按照早到晚的顺序之间的间隔时间最小值尽量大。

解法：最小时间尽量大应该采用二分的方法比较好，然后就变成了判别某个时间间隔m是不是符合要求的了。

为没加飞机设立一个变量xi，0表示早，1表示晚，然后每架飞机i用两个点2*i,2*i+1表示，前者如果被标记表

示早，后者被标记表示晚降。 然后对不同的飞机的起降时间中间隔小于m的i，j建立约束条件，例如：i架飞机

早降间隔和j架飞机的早降时间间隔小于m，那么约束条件就可以在图中这样表示：建立两条边2*i—>2*j+1,

2*j->2*i+1，表示如果i早降则j必须晚降，j早降i必须晚降。

///UVALIVE 3211

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4000010;
struct TwoSAT{
    int n;
    vector<int>G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2], c;
    bool dfs(int x){
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x]=1;
        S[c++]=x;
        for(int i=0; i<G[x].size(); i++){
            if(!dfs(G[x][i])) return false;
        }
        return true;
    }
    void init(int n){
        this->n = n;
        for(int i=0; i<n*2; i++) G[i].clear();
        memset(mark, 0, sizeof(mark));
    }
    void addedge(int x, int xval, int y, int yval){
        x = x*2+xval;
        y = y*2+yval;
        G[x^1].push_back(y);
        G[y^1].push_back(x);
    }
    bool solve(){
        for(int i=0; i<n*2; i+=2){
            if(!mark[i]&&!mark[i+1]){
                c=0;
                if(!dfs(i)){
                    while(c>0) mark[S[--c]]=false;
                    if(!dfs(i+1)) return false;
                }
            }
        }
        return true;
    }
}twosat;

int n, T[maxn][2];
bool check(int mid){
    twosat.init(n);
    for(int i=0; i<n; i++){
        for(int a=0; a<2; a++){
            for(int j=i+1; j<n; j++){
                for(int b=0; b<2; b++){
                    if(abs(T[i][a]-T[j][b])<mid){
                        twosat.addedge(i,a^1,j,b^1);
                    }
                }
            }
        }
    }
    return twosat.solve();
}

int main(){
    while(scanf("%d", &n)!=EOF&&n){
        int l = 0, r = 0;
        for(int i=0; i<n; i++){
            for(int a=0; a<2; a++){
                scanf("%d", &T[i][a]);
                r=max(r,T[i][a]);
            }
        }
        int ans = 0;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d\n", ans);
    }
    return 0;
}