记录编号	26526	评测结果	AAAWWWATTT
题目名称	遥远的距离	最终得分	40
用户昵称	老虎小飞	是否通过	未通过
代码语言	Pascal	运行时间	5.058 s
提交时间	2011-07-24 20:15:35	内存使用	4.69 MiB

var
t0,tt,n,m,i,j,max,t:longint;
tmp,tmp0:extended;
ans:int64;
x,y:array[0..200000]of int64;
a,b:array[0..200000]of longint;

procedure kp(l,r:longint);
var
i,j,t,m:longint;
begin
    i:=l;j:=r;m:=a[(i+j) div 2];
    repeat
        while (x[a[i]]<x[m]) or ((x[a[i]]=x[m])and(y[a[i]]<y[m])) do inc(i);
        while (x[a[j]]>x[m]) or ((x[a[j]]=x[m])and(y[a[j]]>y[m])) do dec(j);
        if i<=j then begin
            t:=a[i];a[i]:=a[j];a[j]:=t;
            inc(i);dec(j);
        end;
    until i>j;
    if i<r then kp(i,r);
    if l<j then kp(l,j);
end;

function xxx(a,b,c,d:longint):int64;
var
x1,x2,y1,y2:int64;
begin
    x1:=x[b]-x[a];y1:=y[b]-y[a];
    x2:=x[d]-x[c];y2:=y[d]-y[c];
    xxx:=x1*y2-x2*y1;
end;

function long(a,b:longint):extended;
var
  z:extended;
begin
    z:=sqr(x[a]-x[b])+sqr(y[a]-y[b]);
    z:=sqrt(z);
    exit(z);
end;

function xian(a,b,c:longint):extended;
var
m:int64;
l:extended;
begin
    m:=abs(xxx(a,b,a,c));
    l:=long(a,b);
    if l=0 then exit(long(a,c));
    xian:=m/l;
end;

procedure chang(a,b,c:longint);
var
n:int64;
begin
    n:=sqr(x[a]-x[c])+sqr(y[a]-y[c]);
    if ans<n then ans:=n;
    n:=sqr(x[c]-x[b])+sqr(y[c]-y[b]);
    if ans<n then ans:=n;
end;

begin
assign(input,'faraway.in');reset(input);
assign(output,'faraway.out');rewrite(output);
    read(t0);
    for tt:=1 to t0 do begin
        read(n,m);
        for i:=1 to n+m do begin
            read(x[i],y[i]);
            a[i]:=i;
        end;
        if n+m=2 then begin
            writeln(long(1,2):0:3);continue;
        end;
        if n=1 then begin
            tmp:=0;
            for i:=1 to m do
                if long(1,i+1)>tmp then tmp:=long(1,i+1);
            writeln(tmp:0:3);
            continue;
        end;
        kp(1,n+m);
        b[1]:=a[1];
        i:=2;
        //while (y[a[i]]>y[a[1]]) and (i<=n+m) do inc(i);
        b[2]:=a[i];t:=2;
        //if i>n+m then begin max:=2;b[2]:=b[n+m];end;
            inc(i);
            while i<=n+m do begin
                if xxx(b[t],a[i],b[t],b[t-1])>=0 then begin
                    inc(t);
                    b[t]:=a[i];
                end
                else begin
                    b[t]:=a[i];
                    while (t>2) and (xxx(b[t-1],a[i],b[t-1],b[t-2])<0) do begin
                        dec(t);b[t]:=a[i];
                    end;
                end;
                inc(i);
            end;
            max:=t;
        i:=n+m-1;
        if i<>1 then begin
            inc(t);
            b[t]:=a[i];
            dec(i);
            while i>=1 do begin
                if xxx(b[t],a[i],b[t],b[t-1])>=0 then begin
                    inc(t);
                    b[t]:=a[i];
                end
                else begin
                    b[t]:=a[i];
                    while (t>2) and (xxx(b[t-1],a[i],b[t-1],b[t-2])<0) do begin
                        dec(t);b[t]:=a[i];
                    end;
                end;
                dec(i);
            end;
        end;
        dec(t);
        i:=1;
        while b[i]>n do inc(i);
        j:=i-2;
        ans:=0;
        if j<=0 then j:=j+t;
        while b[i+1]<=n do begin
            tmp:=xian(b[i],b[i mod t +1],b[j]);
            tmp0:=xian(b[i],b[i mod t +1],b[j mod t+1]);
            while (tmp-tmp0>=0.000001)and(b[j mod t+1]>n) do begin
                j:=j-1;
                if j=0 then j:=t;
                tmp0:=tmp;
                tmp:=xian(b[i],b[i mod t +1],b[j]);
            end;
            chang(b[i],b[i mod t +1],b[j mod t+1]);
            i:=i mod (n+m)+1;
        end;
        tmp:=ans;
        writeln(sqrt(tmp):0:3);
    end;
    close(input);close(output);
end.