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.

Download