2749.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#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( "-1\n" );
		return 0;
	}

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

	printf( "%d\n", b );

	return 0;
}