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;
}