记录编号	26306	评测结果	EEEEEE
题目名称	圣诞节	最终得分	0
用户昵称	ybh	是否通过	未通过
代码语言	Pascal	运行时间	0.000 s
提交时间	2011-07-23 16:03:52	内存使用	9.69 MiB

program christmas;
const
  maxn=2000;
  maxm=500000;
type
  node=record
    v,next:longint;
  end;
var
  list,path,a1,a2:array[0..maxn] of longint;
  edge:array[0..maxm,1..3] of longint;
  map:array[0..maxm] of node;
  b,flag:array[0..maxn] of boolean;
  n,m,e,tt,maxflow,i,j:longint;
  
procedure sort(l,r:longint);
var
  i,j,x,y:longint;
begin
  x:=edge[(l+r) div 2,3];
  i:=l;
  j:=r;
  repeat
    while (edge[i,3]<x) do inc(i);
    while (edge[j,3]>x) do dec(j);
    if i<=j then
    begin
      y:=edge[i,1]; edge[i,1]:=edge[j,1]; edge[j,1]:=y;
      y:=edge[i,2]; edge[i,2]:=edge[j,2]; edge[j,2]:=y;
      y:=edge[i,3]; edge[i,3]:=edge[j,3]; edge[j,3]:=y;
      inc(i); dec(j);
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

procedure addedge(i,j:longint);  
begin  
  inc(e);  
  map[e].v:=j;  
  map[e].next:=list[i];  
  list[i]:=e;  
  
  inc(e);  
  map[e].v:=i;  
  map[e].next:=list[j];  
  list[j]:=e;  
end;

function find(i:longint):boolean;
var
  j,u:longint;
begin
  u:=list[i];
  while u<>0 do
  begin
    j:=map[u].v;
    if not b[j] then
    begin
      b[j]:=true;
      if (path[j]=0) or (find(path[j])) then
      begin
        path[j]:=i;
        exit(true);
      end;
    end;
    u:=map[u].next;
  end;
  exit(false);
end;

procedure hungary;
var
  i:longint;
begin
  for i:=1 to n do
    if not flag[i] then
    begin
      fillchar(b,sizeof(b),0);
      if find(i) then 
      begin
        inc(maxflow);
        flag[i]:=true;
      end;
    end;
end;

begin
  assign(input,'christmas.in');
  reset(input);
  assign(output,'christmas.out');
  rewrite(output);
  
  readln(n);
  for i:=1 to n+n do
    readln(a1[i],a2[i]);
  m:=0;
  for i:=1 to n do
    for j:=n+1 to n+n do
    begin
      inc(m);
      edge[m,1]:=i;
      edge[m,2]:=j;
      edge[m,3]:=sqr(a1[i]-a1[j])+sqr(a2[i]-a2[j]);
    end;
  sort(1,m);
  
  e:=0;
  tt:=0;
  fillchar(list,sizeof(list),0);
  maxflow:=0;
  fillchar(path,sizeof(path),0);
  fillchar(flag,sizeof(flag),false);
  while maxflow<n do
  begin
    inc(tt);
    addedge(edge[tt,1],edge[tt,2]);
    while edge[tt+1,3]=edge[tt,3] do
    begin
      inc(tt);
      addedge(edge[tt,1],edge[tt,2]);
    end;
    hungary;
  end;
  writeln(edge[tt,3]);
  
  close(input);
  close(output);
end.