Poj Solution 2749

http://poj.org/problem?id=2749

#include "stdio.h"
#include "memory.h"
#include "vector"
#include "algorithm"
#include "functional"
#include "math.h"
#define max asdfds
using namespace std;


const int SIZE = 700;
typedef pair<int,int> pair_int;

int sign[SIZE*2], MS;
pair_int e[SIZE*2][SIZE*2], _e[SIZE*2][SIZE*2];
int en[SIZE*2], _en[SIZE*2];

int n;

void init( ) {
    int i;
    MS = 0;
    for( i=0; i<n*2; i++ ) {
        en[i] = 0;
        _en[i] = 0;
    }
}

inline void insert( int u1, int u2, bool f1, bool f2, int v ) {
    // u1^f1 + u2^f2 = 1
    // with value v;
    int u10 = u1+f1*n, u11 = u1+(!f1)*n, u20 = u2+f2*n, u21 = u2+(!f2)*n;
    e[ u11 ][ en[u11]++ ] = pair_int( v, u20 );
    e[ u21 ][ en[u21]++ ] = pair_int( v, u10 );
    _e[ u20 ][ _en[u20]++ ] = pair_int( v, u11 );
    _e[ u10 ][ _en[u10]++ ] = pair_int( v, u21 );
}

void sort_edge( ) {
    int i;
    for( i=0; i<n*2; i++ ) {
        sort( e[i], e[i]+en[i], greater<pair_int>() );
        sort( _e[i], _e[i]+_en[i], greater<pair_int>() );
    }
}

int st[ SIZE*2 ] = { 0 }, sn;
int max, A, B, temp;

void search1( int k ) {
    int i;
    sign[k] = MS;
    for( i=0; i<en[k] && e[k][i].first>max; i++ ) {
        if( sign[ e[k][i].second ] < MS )
            search1( e[k][i].second );
        }
    st[ sn++ ] = k;
}

bool search2( int k ) {
    int i;

    if( sign[(k+n)%(2*n)] == MS )
        return true;

    sign[k] = MS;
    for( i=0; i<_en[k] && _e[k][i].first>max; i++ )
        if( sign[ _e[k][i].second ] <= temp ) {
            if( search2( _e[k][i].second ) )
                return true;
        }

    return false;
}

bool check( int ans ) {
    MS++;
    max = ans;
    sn = 0;

    int i;
    for( i=0; i<2*n; i++ )
        if( sign[i] < MS )
            search1( i );
    
    temp = MS;
    while( sn-- ) {
        if( sign[ st[sn] ] <= temp ) {
            MS ++;
            if( search2( st[sn] ) )
                return false;
        }
    }

    return true;
}

int sx[2], sy[2], s01;
int x[1000], y[1000];
int longest;

void input( ) {
    int a, b, i, j, l[2][2];
    scanf( "%d%d%d", &n, &A, &B );

    init( );    

    scanf( "%d%d%d%d", &sx[0], &sy[0], &sx[1], &sy[1] );
    s01 = abs( sx[0] - sx[1] ) + abs( sy[0] - sy[1] );

    for( i=0; i<n; i++ )
        scanf( "%d%d", x+i, y+i );

    for( i=0; i<A; i++ ) {
        scanf( "%d%d", &a, &b );
        a--, b--;
        insert( a, b, 0, 0, 1000000000 );
        insert( a, b, 1, 1, 1000000000 );
    }

    for( i=0; i<B; i++ ) {
        scanf( "%d%d", &a, &b );
        a--, b--;
        insert( a, b, 1, 0, 1000000000 );
        insert( a, b, 0, 1, 1000000000 );
    }
    longest = 0;
    for( i=0; i<n; i++ ) {
        l[0][0] = abs( x[i] - sx[0] ) + abs( y[i] - sy[0] );
        l[0][1] = abs( x[i] - sx[1] ) + abs( y[i] - sy[1] );

        if( l[0][0] > longest )
            longest = l[0][0];
        if( l[0][1] > longest )
            longest = l[0][1];

        for( j=i+1; j<n; j++ ) {
            l[1][0] = abs( x[j] - sx[0] ) + abs( y[j] - sy[0] );
            l[1][1] = abs( x[j] - sx[1] ) + abs( y[j] - sy[1] );
            insert( i, j, 1, 1, l[0][0]+l[1][0] );
            insert( i, j, 0, 0, l[0][1]+l[1][1] );
            insert( i, j, 1, 0, l[0][0]+l[1][1]+s01 );
            insert( i, j, 0, 1, l[0][1]+l[1][0]+s01 );
        }
    }
    sort_edge( );

}

int main( ) {
    int a, b, c;

    input( );

    a = longest; b = longest*2 + s01;

    if( !check( b ) ) {
        printf( "-1n" );
        return 0;
    }

    while( b - a > 1 ) {
        c = ( b + a ) / 2;
        if( check( c ) )
            b = c;
        else
            a = c;
    }

    printf( "%dn", b );

    return 0;
}