比赛 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.