记录编号	26260	评测结果	EEEEEE
题目名称	圣诞节	最终得分	0
用户昵称	reamb	是否通过	未通过
代码语言	Pascal	运行时间	0.003 s
提交时间	2011-07-23 14:31:20	内存使用	12.79 MiB

program shengdanjie;
var
  gg,g,cost:array[0..1002,0..1002]of longint;
  a:array[1..300000]of longint;
  d,vd:array[0..1003] of longint;
  n,i,j,money,ans,p,k,v:longint;
  h,age:array[0..1003]of longint;
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 not(i>j) then
    begin
      y:=a[i];
      a[i]:=a[j];
      a[j]:=y;
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then
    sort(l,j);
  if i<r then
    sort(i,r);
end;
function min(a,b:longint):longint;
begin
  if a<b then
    min:=a
  else
    min:=b
end;
function dfs(u,flow:longint):longint;
var
  z,v,tmp:longint;
begin
  if u=2*n+1 then
    exit(flow);
  z:=0;
  for v:=0 to 2*n+1 do
    if (g[u,v]>0)and(d[u]=d[v]+1) then
    begin
      tmp:=dfs(v,min(flow-z,g[u,v]));
      g[u,v]:=g[u,v]-tmp;
      g[v,u]:=g[v,u]+tmp;
      z:=z+tmp;
      if z=flow then
        exit(z)
    end;
  if d[0]>=2*n+2 then
    exit(z);
  dec(vd[d[u]]);
  if vd[d[u]]=0 then
    d[0]:=2*n+2;
  inc(d[u]);
  inc(vd[d[u]]);
  exit(z)
end;
begin
  assign (input,'christmas.in');
  reset (input);
  assign (output,'christmas.out');
  rewrite (output);
    readln (n);
    for i:=1 to 2*n do
      readln (h[i],age[i]);
    for i:=1 to n do
      for j:=n+1 to 2*n do
      begin
        inc(p);
        a[p]:=sqr(h[i]-h[j])+sqr(age[i]-age[j]);
        cost[i,j]:=a[p]
      end;
    sort(1,p);
    for i:=1 to n do
      g[0,i]:=1;
    for i:=n+1 to 2*n do
      g[i,2*n+1]:=1;
    for k:=n to p do
    begin
      v:=a[k];
      for i:=1 to n do
      for j:=n+1 to 2*n do
        if cost[i,j]<=v then
          g[i,j]:=1
        else
          g[i,j]:=0;

    fillchar(d,sizeof(d),0);
    fillchar(vd,sizeof(vd),0);
    vd[0]:=2*n+2;
    ans:=0;
    while d[0]<2*n+2 do
    begin
      ans:=ans+dfs(0,maxlongint)
    end;
      if ans=n then
      begin
       writeln(v)  ;
       close (input);
       close (output)
      end
    end;

end.