CASTLE - Xây dựng lâu đài

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      maxn=5010;
type ar=array[1..maxn] of longint;
var n,nx,ny:longint;
    smax,smin,re,cmax,cmin,oo:qword;
    a,b,e,d,x,y:ar;
    f,g,h:array[1..maxn,1..maxn] of integer;

procedure rf;
var i:longint;
begin
     read(n);
     for i:=1 to n do
     begin
          read(a[i],b[i]);
          x[i]:=a[i]; y[i]:=b[i];
          d[i]:=i; e[i]:=i;
     end;
end;

procedure sort(var x,d:ar;l,r:longint);
var i,j,t,u,v:longint;
begin
     i:=l; j:=r; t:=x[(i+j) shr 1]; u:=d[(i+j) shr 1];
     repeat
           while (x[i]<t) or ((x[i]=t) and (d[i]<u)) do i:=i+1;
           while (x[j]>t) or ((x[j]=t) and (d[j]>u)) do j:=j-1;
           if i<=j then
           begin
                v:=x[i]; x[i]:=x[j]; x[j]:=v;
                v:=d[i]; d[i]:=d[j]; d[j]:=v;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(x,d,i,r);
     if l<j then sort(x,d,l,j);
end;

procedure edit(var x,d,a:ar;var nx:longint);
var i:longint;
begin
     nx:=1; a[d[1]]:=1;
     for i:=2 to n do
     begin
          if x[i]>x[nx] then
          begin
               inc(nx);
               x[nx]:=x[i];
          end;
          a[d[i]]:=nx;
     end;
end;

procedure pr;
var i,j,last:longint; s,ss:qword;
begin
     oo:=2000000000;
     oo:=oo*oo*4;
     last:=1; smin:=oo;
     for i:=2 to n do
       if a[i]=a[last] then
       begin
            for j:=last to i-1 do
            begin
                 if f[b[j],b[i]]>0 then
                 begin
                      re:=re+f[b[j],b[i]];
                      s:=y[b[i]]-y[b[j]];
                      ss:=s*(x[a[i]]-x[h[b[j],b[i]]]);
                      s:=s*(x[a[i]]-x[g[b[j],b[i]]]);
                      if s=smax then inc(cmax);
                      if s>smax then
                      begin
                           smax:=s; cmax:=1;
                      end;
                      if ss=smin then inc(cmin);
                      if ss<smin then
                      begin
                           smin:=ss; cmin:=1;
                      end;
                 end
                 else g[b[j],b[i]]:=a[i];
                 inc(f[b[j],b[i]]);
                 h[b[j],b[i]]:=a[i];
            end;
       end
       else last:=i;
     writeln(re);
     if re>0 then
     begin
          writeln(smax,' ',cmax);
          writeln(smin,' ',cmin);
     end;
end;

begin
     assign(input,fi); reset(input);
     rf;
     sort(x,d,1,n);
     edit(x,d,a,nx);
     sort(y,e,1,n);
     edit(y,e,b,ny);
     sort(a,b,1,n);
     pr;
     close(input);
end.

Download