记录编号	26299	评测结果	EEEEEE
题目名称	圣诞节	最终得分	0
用户昵称	Yoghurt	是否通过	未通过
代码语言	Pascal	运行时间	0.004 s
提交时间	2011-07-23 15:59:07	内存使用	16.04 MiB

{
Problem:
Arithmetic Analysis:
Writer:
Data:
Remark:
AC:
}
program christmas;
const
        filename='christmas';
        maxn=2000;
type
        xx=record
                high,age:longint;
        end;
var
        boy,girl:array[0..maxn] of xx;
        a:array[0..maxn,0..maxn] of boolean;
        value:array[0..maxn,0..maxn] of longint;
        cover:array[0..maxn] of boolean;
        link:array[0..maxn] of longint;
        n,left,right,mid:longint;

procedure init;
var
        i,j:longint;
begin
        readln(n);
        for i:=1 to n do
                readln(boy[i].high,boy[i].age);
        for i:=n+1 to 2*n do
                readln(girl[i].high,girl[i].age);
        right:=0;
        for i:=1 to n do
        for j:=n+1 to 2*n do
        begin
                value[i,j]:=sqr(boy[i].high-girl[j].high)+sqr(boy[i].age-girl[j].age);
                if value[i,j]>right then
                        right:=value[i,j];
        end;
end;

procedure addedge(v:longint);
var
        i,j:longint;
begin
        fillchar(a,sizeof(a),false);
        for i:=1 to n do
        for j:=n+1 to 2*n do
                if value[i,j]<=v then
                begin
                        a[i,j]:=true;
                        a[j,i]:=true;
                end;
end;

function find(i:longint):boolean;
var
        k:longint;
begin
        for k:=n+1 to 2*n do
                if (a[i,k]) and (not cover[k]) then
                begin
                        cover[k]:=true;
                        if (link[k]=0) or (find(link[k])) then
                        begin
                                link[k]:=i;
                                exit(true);
                        end;
                end;
        exit(false);
end;

procedure solve;
var
        i,tot:longint;
begin
        left:=0;
        while left<right do
        begin
                mid:=(left+right) div 2;
                addedge(mid);
                fillchar(link,sizeof(link),0);
                tot:=0;
                for i:=1 to n do
                begin
                        fillchar(cover,sizeof(cover),false);
                        if find(i) then
                                inc(tot);
                end;
                if tot=n then right:=mid
                         else left:=mid+1;
        end;
end;

begin
        assign(input,filename+'.in'); reset(input);
        assign(output,filename+'.out'); rewrite(output);

        init;
        solve;
        writeln(right);

        close(input); close(output);
end.