二分法 + 2sat

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
using namespace std;

#define min(a, b)  ((a) < (b) ? (a):(b))
#define max(a, b)  ((a) > (b) ? (a):(b))

#define MAXIN 500

int N, A, B;
int sx1, sy1, sx2, sy2;
int xy[MAXIN][2];
int Dij;
bool G[MAXIN*2][MAXIN*2];
bool TG[MAXIN*2][MAXIN*2];
bool Gr[MAXIN*2][MAXIN*2];
bool TGr[MAXIN*2][MAXIN*2];
bool visited[MAXIN*2];
int finished[MAXIN*2];
int  cid[MAXIN*2];
unsigned long ans;
void fDFS(int i)
{
	static index = 0;	
	visited[i] = true;
    int k;
	for(k = 0; k < 2*N; k ++)
	{
		if(G[i][k] && !visited[k])
              fDFS(k);
	}
	finished[index++] = i;
}
void bDFS(int i, int id)
{
	visited[i] = false;
	cid[i] = id;
	int k;
	for(k = 0; k < 2*N; k ++)
	{
		if(Gr[i][k] && visited[k])
              bDFS(k, id);
	}	
}
bool check()
{ 
    int i;
 	for(i = 0; i < 2*N; i ++)
		if(!visited[i])
	        fDFS(i);
	int id = 0;
	for(i = 2*N - 1; i >= 0; i --)
		if(visited[finished[i]])
		   bDFS(finished[i], id ++);
	for(i = 0; i < N; i ++)
	{
		if(cid[2*i] == cid[2*i + 1])
			return false;
	}
	return  true;
}
bool checkdist(int mid)
{
    int i, j;
	for(i = 0; i < N; i ++)
	  for(j = i + 1; j < N; j ++)
	  {	
		  if(xy[i][0] + xy[j][0] > mid)
		  { 
			  G[2*i][2*j + 1] = 1;
			  Gr[2*j + 1][2*i] = 1;
              G[2*j][2*i + 1] = 1;
			  Gr[2*i + 1][2*j] = 1;
		  }
		  if(xy[i][1] + xy[j][1] > mid)
		  {
			  G[2*i + 1][2*j] = 1;
              Gr[2*j][2*i + 1] = 1;
			  G[2*j + 1][2*i] = 1;
			  Gr[2*i][2*j + 1] = 1;
		  }
		  if(xy[i][0] + Dij + xy[j][1] > mid)
		  {
			  G[2*i][2*j] = 1;
			  Gr[2*j][2*i] = 1;
			  G[2*j + 1][2*i + 1] = 1;
			  Gr[2*i + 1][2*j + 1] = 1;
		  }
		  if(xy[i][1] + Dij + xy[j][0] > mid)
		  {
			  G[2*i + 1][2*j + 1] = 1;
			  Gr[2*j + 1][2*i + 1] = 1;
			  G[2*j][2*i] = 1;
			  Gr[2*i][2*j] = 1;
		  }
	  }
	 return check();
}
void main()
{
    memset(G, 0, 1000*1000);
    memset(TG, 0, 1000*1000);
	memset(Gr, 0, 1000*1000);
	memset(TGr, 0, 1000*1000);
	memset(visited, 0, 1000);
	scanf("%d %d %d", &N, &A, &B);
	scanf("%d %d %d %d", &sx1, &sy1, &sx2, &sy2);
	int i, j;
	for(i = 0; i < N; i ++)
	{
		scanf("%d %d", &xy[i][0], &xy[i][1]);
	}
	int t1, t2;
	for(i = 0; i < A; i ++)
	{
        scanf("%d %d", &t1, &t2);
		t1 --;
		t2 --;
		G[t1*2 + 1][t2*2] = G[t2*2][t1*2 + 1] = 1;
		G[t2*2 + 1][t1*2] = G[t1*2][t2*2 + 1] = 1;  
		Gr[t1*2 + 1][t2*2] = Gr[t2*2][t1*2 + 1] = 1;
		Gr[t2*2 + 1][t1*2] = Gr[t1*2][t2*2 + 1] = 1;	
	}
	for(i = 0; i < B; i ++)
	{
        scanf("%d %d", &t1, &t2);
		t1 --;
		t2 --;
		G[t1*2 + 1][t2*2 + 1] = G[t2*2 + 1][t1*2 + 1] = 1;
		G[t2*2][t1*2] = G[t1*2][t2*2] = 1; 
		Gr[t1*2 + 1][t2*2 + 1] = Gr[t2*2 + 1][t1*2 + 1] = 1;
		Gr[t2*2][t1*2] = Gr[t1*2][t2*2] = 1; 
	}

    if(!check())
       printf("-1\n");
	else
	{
		for(i = 0; i < 2*N; i ++)
		  for(j = 0; j < 2*N; j ++)
		  {
			  TG[i][j] = G[i][j];
			  TGr[i][j] = Gr[i][j];
		  }
		  
		Dij = abs(sx1 - sx2) + abs(sy1 - sy2);
		int max1 = 0, max2 = 0;
	 	for(i = 0; i < N; i ++)
		{
			t1 = abs(xy[i][0] - sx1) + abs(xy[i][1] - sy1);
			t2 = abs(xy[i][0] - sx2) + abs(xy[i][1] - sy2);
			xy[i][0] = t1;
			xy[i][1] = t2;
			max1 = max(xy[i][0], max1);
			max2 = max(xy[i][1], max2);
		}	  
	    int high = max(max1 + max2 + Dij, max1*2);
		high = max(high, max2*2);
		int low = 0;
		int mid;
		while(high > low)
		{
            mid = (high + low)/2;

			if(checkdist(mid))
				high = mid;
			else
				low = mid + 1;

		    for(i = 0; i < 2*N; i ++)
		      for(j = 0; j < 2*N; j ++)
			  {
			    G[i][j] = TG[i][j];
			    Gr[i][j] = TGr[i][j];
			  }
		}
		printf("%d\n", high);
	}
}