记录编号	38441	评测结果	AAAAAT
题目名称	圣诞节	最终得分	83
用户昵称	wo shi 刘畅	是否通过	未通过
代码语言	Pascal	运行时间	1.019 s
提交时间	2012-04-18 21:24:32	内存使用	27.78 MiB

var
  n,i,j,m,zhong:longint;
  a,b,x,y,xx,yy:array[0..1000000]of longint;
  g:array[0..1000,0..1000]of longint;
  c:Array[0..1000000]of boolean;

procedure sort(l,r:longint);
var
  i,j,x,y:longint;
begin
  i:=l;
  j:=r;
  x:=a[(l+r) div 2];
  repeat
    while a[i]<x do inc(i);
    while x<a[j] do dec(j);
    if i<=j then
    begin
      y:=a[i];
      a[i]:=a[j];
      a[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;

function hungary(u:longint):boolean;
var
  v:longint;
begin
  for v:=1 to n do
  if (not c[v])and(g[u,v]<=zhong) then
  begin
    c[v]:=true;
    if (b[v]=0)or(hungary(b[v])) then
    begin
      b[v]:=u;
      exit(true);
    end;
  end;
  exit(false);
end;

function ok:boolean;
var
  i,j,now:longint;
begin
  for i:=1 to n do b[i]:=0;
  now:=0;
  for i:=1 to n do
  begin
    for j:=1 to n do c[j]:=false;
    if hungary(i) then inc(now);
  end;
  if now=n then exit(true);
  exit(false);
end;

procedure erfen(l,r:longint);
var
  mid:longint;
begin
  if l=r then
  begin
    writeln(a[l]);
    exit;
  end;
  mid:=(l+r) div 2;
  zhong:=a[mid];
  if ok then erfen(l,mid)
  else erfen(mid+1,r);
end;

begin
  assign(input,'christmas.in'); reset(input);
  assign(output,'christmas.out'); rewrite(output);
  readln(n);
  for i:=1 to n do readln(x[i],y[i]);
  for i:=1 to n do readln(xx[i],yy[i]);
  for i:=1 to n do
   for j:=1 to n do
   begin
     inc(m);
     a[m]:=sqr(x[i]-xx[j])+sqr(y[i]-yy[j]);
     g[i,j]:=a[m];
   end;
  sort(1,m);
  erfen(1,m);
  close(input);
  close(output);
end.