CASTLE - Xây dựng lâu đài
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$R-,Q-}
uses math;
const
FINP='';
FOUT='';
MAXN=5001;
oo=1000000000000000;
type
list=^node;
node=record
u:longint;
next:list;
end;
var
f1,f2:text;
n:longint;
ds:array[1..MAXN] of list;
c,ind,x,y:array[1..MAXN] of longint;
count,smax,smin,cmax,cmin:int64;
procedure openF; inline;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
close(f1); close(f2);
end;
procedure inp; inline;
var
i:longint;
begin
read(f1,n);
for i:=1 to n do
read(f1,x[i],y[i]);
for i:=1 to n do c[i]:=x[i];
end;
procedure swap(var a,b:longint); inline;
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
var
mid:longint;
procedure sortC(l,r:longint); inline;
var
i,j:longint;
begin
i:=l; j:=r; mid:=c[l+random(r-l+1)];
repeat
while c[i]<mid do inc(i);
while c[j]>mid do dec(j);
if i<=j then
begin
swap(c[i],c[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sortC(i,r);
if l<j then sortC(l,j);
end;
procedure sortY(l,r:longint); inline;
var
i,j:longint;
begin
i:=l; j:=r; mid:=y[l+random(r-l+1)];
repeat
while y[i]>mid do inc(i);
while y[j]<mid do dec(j);
if i<=j then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sortY(i,r);
if l<j then sortY(l,j);
end;
var
gt:longint;
function find(l,r:longint):longint; inline;
begin
if c[l]=gt then exit(l);
if c[r]=gt then exit(r);
mid:=(l+r)>>1;
if c[mid]=gt then exit(mid);
if gt<c[mid] then exit(find(l,mid-1))
else exit(find(mid+1,r));
end;
procedure add(u:longint; var a:list); inline;
var
p:list;
begin
new(p); p^.u:=u;
p^.next:=a; a:=p;
end;
procedure solve;
var
j,i,sl,firsti,firstj,yi,yj,lasti,lastj,cij:longint;
l,ss:int64;
pi,pj:list;
ok:boolean;
begin
//Khoi tao mang gia tri X
sortC(1,n);
sl:=1;
for i:=2 to n do
if c[i]>c[sl] then
begin
inc(sl);
c[sl]:=c[i];
end;
//Khoi tao danh sach cac diem co hoanh do X[i]
sortY(1,n);
for i:=1 to n do
begin
gt:=x[i];
ind[i]:=find(1,sl);
end;
for i:=1 to n do
add(y[i],ds[ind[i]]);
//Dem cac hinh chu nhat thoa man
count:=0; smin:=oo; smax:=-1; cmin:=0; cmax:=0;
for i:=1 to sl-1 do
for j:=i+1 to sl do
begin
pi:=ds[i]; pj:=ds[j]; l:=c[j]-c[i];
firsti:=pi^.u; pi:=pi^.next; firstj:=pj^.u; pj:=pj^.next;
while firsti<>firstj do
begin
if (pi=nil) or (pj=nil) then break;
if firsti<firstj then begin firsti:=pi^.u; pi:=pi^.next; end
else begin firstj:=pj^.u; pj:=pj^.next; end;
end;
if (pi=nil) or (pj=nil) then continue;
lasti:=firsti; lastj:=firstj; yi:=pi^.u; yj:=pj^.u; pi:=pi^.next; pj:=pj^.next;
cij:=1; ok:=true;
while ok do
begin
if (yi<yj) and (pi<>nil) then begin yi:=pi^.u; pi:=pi^.next; end
else if (yi>yj) and (pj<>nil) then begin yj:=pj^.u; pj:=pj^.next; end
else ok:=false;
if yi=yj then
begin
ok:=true;
inc(count,cij);
ss:=l*(yi-lasti);
if ss>0 then
if ss<smin then begin smin:=ss; cmin:=1; end
else if ss=smin then inc(cmin);
lasti:=yi; lastj:=yj; inc(cij);
if (pi=nil) and (pj=nil) then ok:=false;
if pi<>nil then begin yi:=pi^.u; pi:=pi^.next; end;
if pj<>nil then begin yj:=pj^.u; pj:=pj^.next; end;
end;
end;
ss:=l*(lasti-firsti);
if ss>smax then begin smax:=ss; cmax:=1; end
else if ss=smax then inc(cmax);
end;
end;
procedure ans; inline;
begin
writeln(f2,count);
if count=0 then exit;
writeln(f2,smax,' ',cmax);
writeln(f2,smin,' ',cmin);
end;
begin
openF;
inp;
solve;
ans;
closeF;
end.