比赛 |
20110724 |
评测结果 |
WWWTTTWTTT |
题目名称 |
遥远的距离 |
最终得分 |
0 |
用户昵称 |
wo shi 刘畅 |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-24 11:56:36 |
显示代码纯文本
type
jp=array[0..1000000]of longint;
var
n,m,t,la,lb,x,y,time,i,j,topa,top,topb:longint;
ans:double;
yes:boolean;
a,b,pa,pb,aa,bb:jp;
function left(x1,y1,x2,y2:longint):boolean;
begin
if x1*y2-x2*y1<0 then exit(true);
exit(false);
end;
procedure qsort(var a,b:jp; l,r:longint);
procedure sort(l,r:longint);
var
x,y,i,j:longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
y:=b[(l+r) div 2];
repeat
while left(x,y,a[i],b[i]) do inc(i);
while left(a[j],b[j],x,y) do dec(j);
if i<=j then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
y:=b[i];
b[i]:=b[j];
b[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
begin
sort(l,r);
end;
begin
assign(input,'faraway.in'); reset(input);
assign(output,'faraway.out'); rewrite(output);
readln(t);
for time:=1 to t do
begin
readln(n,m);
la:=0;
lb:=0;
for i:=1 to n+m do
begin
readln(x,y);
if x>0 then
begin
inc(la);
a[la]:=x;
b[la]:=y;
end
else begin
inc(lb);
aa[lb]:=x;
bb[lb]:=y;
end;
end;
qsort(a,b,1,la);
qsort(aa,bb,1,lb);
pa[1]:=1;
pa[2]:=2;
top:=2;
while pa[top]<>1 do
begin
yes:=false;
for i:=pa[top]+1 to la do
if left(a[i]-a[pa[top-1]],b[i]-b[pa[top-1]],
a[i]-a[pa[top]],b[i]-b[pa[top]]) then
begin
inc(top);
pa[top]:=i;
yes:=true;
break;
end;
if not yes then dec(top);
end;
dec(top);
topa:=top;
pb[1]:=1;
pb[2]:=2;
top:=2;
while pb[top]<>1 do
begin
yes:=false;
for i:=pb[top]+1 to lb do
if left(aa[i]-aa[pb[top-1]],bb[i]-bb[pb[top-1]],
aa[i]-aa[pb[top]],bb[i]-bb[pb[top]]) then
begin
inc(top);
pb[top]:=i;
yes:=true;
break;
end;
if not yes then dec(top);
end;
dec(top);
topb:=top;
ans:=maxlongint*maxlongint;
for i:=1 to topa do
for j:=1 to topb do
if sqr(a[i]-aa[i])+sqr(b[i]-bb[i])<ans then
ans:=sqr(a[i]-aa[i])+sqr(b[i]-bb[i]);
writeln(sqrt(ans):0:3);
end;
close(input);
close(output);
end.