[UVA] 1146 - Now or later

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define N 2005
struct TwoSAT{
    vector<int> s[N*2];
    int mark[N*2],n;
    stack<int> _stack;
    int dfs(int x){
        if(mark[x^1]) return 0;
        if(mark[x]) return 1;
        mark[x]=1;
        _stack.push(x);
        int i;
        for(i=0;i<s[x].size();i++){
            int v=s[x][i];
            if(!dfs(v)) return 0;
        }
        return 1;
    }
    void init(int n){
        this->n=n;
        int i;
        for(i=0;i<n*2;i++)
            s[i].clear();
        memset(mark,0,sizeof(mark));
    }
    void add(int x,int a,int y,int b){
        x=x*2+a;
        y=y*2+b;
        s[x^1].push_back(y);
        s[y^1].push_back(x);
    }
    int solve(){
        int i;
        for(i=0;i<n*2;i+=2){
            if(!mark[i] && !mark[i+1]){
                if(!dfs(i)){
                    while(_stack.size()){
                        int x=_stack.top();
                        _stack.pop();
                        mark[x]=0;
                    }
                    if(!dfs(i+1)) return 0;
                }
            }
        }
        return 1;
    }
}_TwoSAT;
int price[N][2];
int main(){
    int n,x,y,a,b,i,j,l,r,m;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++)
            scanf("%d%d",&price[i][0],&price[i][1]);
        l=0,r=10000001;
        while(l+1!=r){
            m=(l+r)/2;
            _TwoSAT.init(n);
            for(i=0;i<n;i++)
            for(a=0;a<2;a++)
            for(j=i+1;j<n;j++)
            for(b=0;b<2;b++){
                if(abs(price[i][a]-price[j][b])<m)
                    _TwoSAT.add(i,a^1,j,b^1);
            }
            if(_TwoSAT.solve()) l=m;
            else r=m;
        }
        printf("%d\n",l);
    }
}