万变不离其宗
只要搞清楚题目的基本模型
搞清楚边是一种推导出的关系
搞清楚里面的逻辑关系
那就没什么难的了……
二分+sat，没什么好说的
const inf=;
type node=record
point,next:longint;
end;
var edge:array[..] of node;
v,f:array[..] of boolean;
x,y,be,w1,w2,hx,hy,fx,fy,p,st,dfn,low:array[..] of longint;
sum,w,l,r,ans,a,b,i,n,m,len,h,t:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function dis(i,j:longint):longint;
begin
exit(abs(x[i]-x[j])+abs(y[i]-y[j]));
end;
procedure add(x,y:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end;
procedure tarjan(x:longint);
var i,y:longint;
begin
inc(h);
inc(t);
dfn[x]:=h;
low[x]:=h;
f[x]:=true;
v[x]:=true;
st[t]:=x;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
tarjan(y);
low[x]:=min(low[x],low[y]);
end
else if f[y] then low[x]:=min(low[x],low[y]);
i:=edge[i].next;
end;
if dfn[x]=low[x] then
begin
inc(sum);
while st[t+]<>x do
begin
y:=st[t];
f[y]:=false;
be[y]:=sum;
dec(t);
end;
end;
end;
function check(k:longint):boolean;
var i,x,y,j:longint;
begin
len:=;
fillchar(p,sizeof(p),);
fillchar(v,sizeof(v),false);
fillchar(st,sizeof(st),);
fillchar(be,sizeof(be),);
for i:= to a do
begin
x:=hx[i];
y:=hy[i];
add(x,y+n);
add(x+n,y);
add(y+n,x);
add(y,x+n);
end;
for i:= to b do
begin
x:=fx[i];
y:=fy[i];
add(x,y);
add(y,x);
add(x+n,y+n);
add(y+n,x+n);
end;
for i:= to n- do
for j:=i+ to n do
begin
if w1[i]+w1[j]>k then
begin
add(j,i+n);
add(i,j+n);
end;
if w2[i]+w2[j]>k then
begin
add(i+n,j);
add(j+n,i);
end;
if w1[i]+w+w2[j]>k then
begin
add(i,j);
add(j+n,i+n);
end;
if w2[i]+w+w1[j]>k then
begin
add(i+n,j+n);
add(j,i);
end;
end;
sum:=;
for i:= to *n do
if not v[i] then
begin
h:=;
t:=;
tarjan(i);
end;
for i:= to n do
if be[i]=be[i+n] then exit(false);
exit(true);
end;
begin
readln(n,a,b);
l:=inf;
r:=;
readln(x[n+],y[n+],x[n+],y[n+]);
w:=dis(n+,n+);
for i:= to n do
begin
readln(x[i],y[i]);
w1[i]:=dis(i,n+);
w2[i]:=dis(i,n+);
l:=min(l,min(w1[i],w2[i]));
r:=max(r,max(w1[i],w2[i]));
end;
r:=r shl +w;
for i:= to a do
readln(hx[i],hy[i]);
for i:= to b do
readln(fx[i],fy[i]);
ans:=inf;
while l<=r do
begin
m:=(l+r) shr ;
if check(m) then
begin
ans:=m;
r:=m-;
end
else l:=m+;
end;
if ans=inf then writeln(-) else writeln(ans);
end.
const inf=;
type node=record
point,next:longint;
end;
var edge:array[..] of node;
v,f:array[..] of boolean;
x,y,be,w1,w2,hx,hy,fx,fy,p,st,dfn,low:array[..] of longint;
sum,w,l,r,ans,a,b,i,n,m,len,h,t:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function dis(i,j:longint):longint;
begin
exit(abs(x[i]-x[j])+abs(y[i]-y[j]));
end;
procedure add(x,y:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end;
procedure tarjan(x:longint);
var i,y:longint;
begin
inc(h);
inc(t);
dfn[x]:=h;
low[x]:=h;
f[x]:=true;
v[x]:=true;
st[t]:=x;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
tarjan(y);
low[x]:=min(low[x],low[y]);
end
else if f[y] then low[x]:=min(low[x],low[y]);
i:=edge[i].next;
end;
if dfn[x]=low[x] then
begin
inc(sum);
while st[t+]<>x do
begin
y:=st[t];
f[y]:=false;
be[y]:=sum;
dec(t);
end;
end;
end;
function check(k:longint):boolean;
var i,x,y,j:longint;
begin
len:=;
fillchar(p,sizeof(p),);
fillchar(v,sizeof(v),false);
fillchar(st,sizeof(st),);
fillchar(be,sizeof(be),);
for i:= to a do
begin
x:=hx[i];
y:=hy[i];
add(x,y+n);
add(x+n,y);
add(y+n,x);
add(y,x+n);
end;
for i:= to b do
begin
x:=fx[i];
y:=fy[i];
add(x,y);
add(y,x);
add(x+n,y+n);
add(y+n,x+n);
end;
for i:= to n- do
for j:=i+ to n do
begin
if w1[i]+w1[j]>k then
begin
add(j,i+n);
add(i,j+n);
end;
if w2[i]+w2[j]>k then
begin
add(i+n,j);
add(j+n,i);
end;
if w1[i]+w+w2[j]>k then
begin
add(i,j);
add(j+n,i+n);
end;
if w2[i]+w+w1[j]>k then
begin
add(i+n,j+n);
add(j,i);
end;
end;
sum:=;
for i:= to *n do
if not v[i] then
begin
h:=;
t:=;
tarjan(i);
end;
for i:= to n do
if be[i]=be[i+n] then exit(false);
exit(true);
end;
begin
readln(n,a,b);
l:=inf;
r:=;
readln(x[n+],y[n+],x[n+],y[n+]);
w:=dis(n+,n+);
for i:= to n do
begin
readln(x[i],y[i]);
w1[i]:=dis(i,n+);
w2[i]:=dis(i,n+);
l:=min(l,min(w1[i],w2[i]));
r:=max(r,max(w1[i],w2[i]));
end;
r:=r shl +w;
for i:= to a do
readln(hx[i],hy[i]);
for i:= to b do
readln(fx[i],fy[i]);
ans:=inf;
while l<=r do
begin
m:=(l+r) shr ;
if check(m) then
begin
ans:=m;
r:=m-;
end
else l:=m+;
end;
if ans=inf then writeln(-) else writeln(ans);
end.