记录编号	26472	评测结果	AAAAAAAAAA
题目名称	遥远的距离	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	2.905 s
提交时间	2011-07-24 16:29:41	内存使用	5.46 MiB

{遥远的距离 2011/07/24NOI模拟赛
 计算几何 求平面点集最远点对（错误的题目 错误的算法）
 Author: yangbohua
 Time: 2011-07-24}
 
program faraway;
const
  maxn=200100;
var
  x,y:array[0..maxn] of int64;
  q,q1,c:array[0..maxn] of longint;
  n,m,tot,tot1,i,j,ac100,ac:longint;
  maxlength:int64;
  ans:extended;
    
procedure sort(l,r:longint);
var
  midx,midy,temp:int64;
  i,j,temp1:longint;
begin
  midx:=x[(l+r) div 2];
  midy:=y[(l+r) div 2];
  i:=l;
  j:=r;
  repeat
    while (y[i]<midy) or ((y[i]=midy) and (x[i]<midx)) do inc(i);
    while (y[j]>midy) or ((y[j]=midy) and (x[j]>midx)) do dec(j);
    if i<=j then
    begin
      temp:=x[i]; x[i]:=x[j]; x[j]:=temp;
      temp:=y[i]; y[i]:=y[j]; y[j]:=temp;
      temp1:=c[i]; c[i]:=c[j]; c[j]:=temp1;
      inc(i); dec(j);
    end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;

function cross(a,b,c:longint):int64;
begin
  cross:=(x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a]);
end;

function max(a,b:int64):int64;
begin
  if a>b then max:=a else max:=b;
end;

function dist(a,b:longint):int64;
begin
  dist:=sqr(x[a]-x[b])+sqr(y[a]-y[b]);
end;

begin
  assign(input,'faraway.in');
  reset(input);
  assign(output,'faraway.out');
  rewrite(output);
  
  readln(ac);
  for ac100:=1 to ac do
  begin
    readln(n,m);
    for i:=1 to n+m do
    begin
      readln(x[i],y[i]);
      if x[i]<0 then c[i]:=1 else c[i]:=2;
    end;

    n:=n+m;
    sort(1,n);
  
    tot:=2;
    q[1]:=1;
    q[2]:=2;
    for i:=3 to n do
    begin
      while (tot>=2) and (cross(q[tot-1],q[tot],i)<=0) do dec(tot);
      inc(tot); q[tot]:=i;
    end;
    tot1:=2;
    q1[1]:=1;
    q1[2]:=2;
    for i:=3 to n do
    begin
      while (tot1>=2) and (cross(q1[tot1-1],q1[tot1],i)>=0) do dec(tot1);
      inc(tot1); q1[tot1]:=i;
    end;
    for i:=tot1-1 downto 1 do
    begin
      inc(tot);
      q[tot]:=q1[i];
    end;
    
    maxlength:=0;
    j:=2;
    n:=tot-1;
    for i:=1 to n do
    begin
      while (c[q[j+1]]+c[q[i]]=3) and (abs(cross(q[i],q[i+1],q[j]))<abs(cross(q[i],q[i+1],q[j+1]))) do j:=j mod n+1;
      maxlength:=max(maxlength,max(dist(q[i],q[j]),dist(q[i+1],q[j])));     
    end;
  
    ans:=sqrt(maxlength);
    writeln(ans:0:3);
  end;
  
  close(input);
  close(output);
end.