学步园

传送门：【HDU】1822 Building roads

题目分析：二分 + 2-sat

首先给出的hate关系以及like关系我们先建边。

设x<<1为x选择连接s1，x<<1|1为x选择连接s2。

u hate v : < u , ~v > , < v , ~u > , < ~u , v > , < ~v , u >

u like v : < u , v > , < ~v , ~u > , < v , u > , < ~u , ~v >

接下来二分任意两个农场间的最大距离。

如果两个农场之间的距离超过设定的最大距离，视为冲突，则建边。

设农场x到s1的距离为x_s1，到s2的距离为x_s2，y同理。

设s1到s2的距离为dist，二分的最大距离为mid。

则：

x_s1 + y_s1 > mid : < x , ~y > , < y , ~x >

x_s2 + y_s2 > mid : < ~x , y > , < ~y , x >

x_s1 + y_s2 + dist > mid : < x , y > , < ~y , ~x >

x_s2 + y_s1 + dist > mid : < ~x , ~y > , < y , x >

代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 1005 ;
const int MAXM = 505 ;
const int MAXE = 2333333 ;

struct Edge {
	int v ;
	Edge* next ;
} ;

struct Point {
	int x , y ;
	Point ( int x = 0 , int y = 0 ) : x ( x ) , y ( y ) {}
	Point operator - ( const Point& a ) const {
		return Point ( abs ( x - a.x ) , abs ( y - a.y ) ) ;
	}
	Point operator + ( const Point& a ) const {
		return Point ( x + a.x , y + a.y ) ;
	}
} ;

Edge E[MAXE] , *H[MAXN] , *cur , *pre , *rH[MAXN] ;
int dfn[MAXN] , low[MAXN] , scc[MAXN] , scc_cnt ;
int S[MAXN] , top , dfs_clock ;
int n , hate , like ;

Point s1 , s2 , p_s1[MAXM] , p_s2[MAXM] , tmp ;

void init () {
	cur = pre ;
	top = 0 ;
	scc_cnt = 0 ;
	dfs_clock = 0 ;
	CPY ( H , rH ) ;
	CLR ( dfn , 0 ) ;
	CLR ( scc , 0 ) ;
}

void addedge ( int u , int v ) {
	cur -> v = v ;
	cur -> next = H[u] ;
	H[u] = cur ++ ;
}

void tarjan ( int u ) {
	dfn[u] = low[u] = ++ dfs_clock ;
	S[top ++] = u ;
	for ( Edge* e = H[u] ; e ; e = e -> next ) {
		int v = e -> v ;
		if ( !dfn[v] ) {
			tarjan ( v ) ;
			low[u] = min ( low[u] , low[v] ) ;
		} else if ( !scc[v] ) low[u] = min ( low[u] , dfn[v] ) ;
	}
	if ( low[u] == dfn[u] ) {
		++ scc_cnt ;
		do {
			scc[S[-- top]] = scc_cnt ;
		} while ( u != S[top] ) ;
	}
}

void scanf ( int& x , char c = 0 , bool flag = 0 ) {
	while ( ( c = getchar () ) != '-' && ( c < '0' || c > '9' ) ) ;
	if ( c == '-' ) flag = 1 , c = getchar () ;
	x = c - '0' ;
	while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
	if ( flag ) x = -x ;
}


bool ok () {
	REP ( i , 0 , n << 1 ) if ( !dfn[i] ) tarjan ( i ) ;
	REP ( i , 0 , n ) if ( scc[i << 1] == scc[i << 1 | 1] ) return 0 ;
	return 1 ;
}

int len ( Point a ) {
	return a.x + a.y ;
}

void solve () {
	int u , v ;
	pre = E ;
	CLR ( rH , 0 ) ;
	init () ;
	scanf ( s1.x ) , scanf ( s1.y ) ;
	scanf ( s2.x ) , scanf ( s2.y ) ;
	REP ( i , 0 , n ) {
		scanf ( tmp.x ) , scanf ( tmp.y ) ;
		p_s1[i] = tmp - s1 ;
		p_s2[i] = tmp - s2 ;
	}
	while ( hate -- ) {
		scanf ( u ) , scanf ( v ) ;
		-- u , -- v ;
		addedge ( u << 1 , v << 1 | 1 ) ;
		addedge ( v << 1 , u << 1 | 1 ) ;
		addedge ( u << 1 | 1 , v << 1 ) ;
		addedge ( v << 1 | 1 , u << 1 ) ;
	}
	while ( like -- ) {
		scanf ( u ) , scanf ( v ) ;
		-- u , -- v ;
		addedge ( u << 1 , v << 1 ) ;
		addedge ( v << 1 , u << 1 ) ;
		addedge ( u << 1 | 1 , v << 1 | 1 ) ;
		addedge ( v << 1 | 1 , u << 1 | 1 ) ;
	}
	if ( !ok () ) {
		printf ( "-1\n" ) ;
		return ;
	}
	CPY ( rH , H ) ;
	pre = cur ;
	int l = 0 , r = 12000000 , dist = len ( s1 - s2 ) ;
	while ( l < r ) {
		init () ;
		int m = ( l + r ) >> 1 ;
		REP ( i , 0 , n ) REP ( j , i + 1 , n ) {
			if ( len ( p_s1[i] + p_s1[j] ) > m ) {
				addedge ( i << 1 , j << 1 | 1 ) ;
				addedge ( j << 1 , i << 1 | 1 ) ;
			}
			if ( len ( p_s2[i] + p_s2[j] ) > m ) {
				addedge ( i << 1 | 1 , j << 1 ) ;
				addedge ( j << 1 | 1 , i << 1 ) ;
			}
			if ( len ( p_s1[i] + p_s2[j] ) + dist > m ) {
				addedge ( i << 1 , j << 1 ) ;
				addedge ( j << 1 | 1 , i << 1 | 1 ) ;
			}
			if ( len ( p_s2[i] + p_s1[j] ) + dist > m ) {
				addedge ( i << 1 | 1 , j << 1 | 1 ) ;
				addedge ( j << 1 , i << 1 ) ;
			}
		}
		if ( ok () ) r = m ;
		else l = m + 1 ;
	}
	printf ( "%d\n" , l ) ;
}

int main () {
	while ( ~scanf ( "%d%d%d" , &n , &hate , &like ) ) solve () ;
	return 0 ;
}