rect1.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 86 行

{
ID:maigoak1
PROG:rect1
}

program rect1;
const
  maxn=1000;
  colors=2500;
type
  rect=record
    llx,lly,urx,ury,color:integer;
  end;
var
  fin,fout:text;
  r:array[0..maxn]of rect;
  c:array[1..colors] of longint;
  x,y:array[1..maxn*2+1]of integer;
  a,b,n,nx,ny,i,j,k:integer;
function notinx(t:integer):boolean;
  var
    i:integer;
  begin
    for i:=1 to nx do
      if t=x[i] then begin
        notinx:=false;
        exit;
      end;
    notinx:=true;
  end;
function notiny(t:integer):boolean;
  var
    i:integer;
  begin
    for i:=1 to ny do
      if t=y[i] then begin
        notiny:=false;
        exit;
      end;
    notiny:=true;
  end;
procedure exchange(var p,q:integer);
  var
    t:integer;
  begin
    t:=p;p:=q;q:=t;
  end;
begin
  fillchar(c,sizeof(c),0);
  assign(fin,'rect1.in');
  reset(fin);
  readln(fin,a,b,n);
  r[0].llx:=0;r[0].lly:=0;r[0].urx:=a;r[0].ury:=b;r[0].color:=1;
  nx:=2;ny:=2;
  x[1]:=0;x[2]:=a;y[1]:=0;y[2]:=b;
  for i:=1 to n do begin
    readln(fin,r[i].llx,r[i].lly,r[i].urx,r[i].ury,r[i].color);
    if notinx(r[i].llx) then begin inc(nx);x[nx]:=r[i].llx;end;
    if notinx(r[i].urx) then begin inc(nx);x[nx]:=r[i].urx;end;
    if notiny(r[i].lly) then begin inc(ny);y[ny]:=r[i].lly;end;
    if notiny(r[i].ury) then begin inc(ny);y[ny]:=r[i].ury;end;
  end;
  close(fin);

  for i:=1 to nx-1 do
    for j:=i+1 to nx do
      if x[i]>x[j] then exchange(x[i],x[j]);
  for i:=1 to ny-1 do
    for j:=i+1 to ny do
      if y[i]>y[j] then exchange(y[i],y[j]);

  for i:=1 to nx-1 do
    for j:=1 to ny-1 do
      for k:=n downto 0 do
        if (x[i]>=r[k].llx) and (x[i+1]<=r[k].urx) and (y[j]>=r[k].lly) and (y[j+1]<=r[k].ury) then begin
          c[r[k].color]:=c[r[k].color]+(x[i+1]-x[i])*(y[j+1]-y[j]);
          break;
        end;

  assign(fout,'rect1.out');
  rewrite(fout);
  for i:=1 to colors do
    if c[i]>0 then writeln(fout,i,' ',c[i]);
  close(fout);
end.