window.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:window
}

program window;
type
  edges=array[1..144]of integer;
  bools=array[1..144]of boolean;{True if it's a starting edge}
var
  fin,fout:text;
  x1,y1,x2,y2,lv:array[0..71]of integer;
  exist:array[0..71]of boolean;
  top,bottom,win:integer;
  s:string;
  op:char;
function min(a,b:integer):integer;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:integer):integer;
  begin
    if a>b then max:=a else max:=b;
  end;
procedure exchange(var a,b:integer);
  var
    t:integer;
  begin
    t:=a;a:=b;b:=t;
  end;
function getvalue(var s:string):integer;
  var
    p:word;
    t:string;
    x:integer;
  begin
    val(s,x,p);
    t:=copy(s,1,p-1);
    delete(s,1,p);
    val(t,x,p);
    getvalue:=x;
  end;
function id(c:char):byte;
  begin
    if c<'A' then
      id:=ord(c)-48
    else if c<'a' then
      id:=ord(c)-55
    else
      id:=ord(c)-61
  end;
procedure qsort(var a:edges;var b:bools;s,t:byte);
  var
    p,i,j:byte;
    tint:integer;
    tbool:boolean;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tint:=a[p];tbool:=b[p];
    a[p]:=a[s];b[p]:=b[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (a[j]>=tint) do dec(j);
      if i=j then break;
      a[i]:=a[j];b[i]:=b[j];inc(i);
      while (i<j) and (a[i]<=tint) do inc(i);
      if i=j then break;
      a[j]:=a[i];b[j]:=b[i];dec(j);
    until i=j;
    a[i]:=tint;b[i]:=tbool;
    qsort(a,b,s,i-1);
    qsort(a,b,i+1,t);
  end;
procedure cal(win:byte);
  var
    h,w:edges;
    bh,bw:bools;
    ch,cw,lh,lw:byte;
    i,j,height:integer;
    area,visible:longint;
  begin
    area:=(x2[win]-x1[win])*(y2[win]-y1[win]);
    visible:=area;
    lh:=0;
    for i:=0 to 71 do begin
      if not exist[i] then continue;
      if lv[i]<=lv[win] then continue;
      if (x1[i]>=x2[win]) or (x2[i]<=x1[win]) or
         (y1[i]>=y2[win]) or (y2[i]<=y1[win]) then continue;
      inc(lh);h[lh]:=max(y1[i],y1[win]);bh[lh]:=true;
      inc(lh);h[lh]:=min(y2[i],y2[win]);bh[lh]:=false;
    end;
    qsort(h,bh,1,lh);
    ch:=0;
    for i:=1 to lh-1 do begin
      if bh[i] then inc(ch) else dec(ch);
      if h[i]=h[i+1] then continue;
      if ch=0 then continue;
      height:=h[i+1]-h[i];
      lw:=0;
      for j:=0 to 71 do begin
        if not exist[j] then continue;
        if lv[j]<=lv[win] then continue;
        if (x1[j]>=x2[win]) or (x2[j]<=x1[win]) or
           (y1[j]>=h[i+1]) or (y2[j]<=h[i]) then continue;
        inc(lw);w[lw]:=max(x1[j],x1[win]);bw[lw]:=true;
        inc(lw);w[lw]:=min(x2[j],x2[win]);bw[lw]:=false;
      end;
      qsort(w,bw,1,lw);
      cw:=0;
      for j:=1 to lw-1 do begin
        if bw[j] then inc(cw) else dec(cw);
        if cw=0 then continue;
        dec(visible,(w[j+1]-w[j])*height);
      end;
    end;
    writeln(fout,visible/area*100:0:3);
  end;
begin
  assign(fin,'window.in');
  reset(fin);
  assign(fout,'window.out');
  rewrite(fout);

  fillchar(exist,sizeof(exist),0);
  top:=0;bottom:=1;
  repeat
    readln(fin,s);
    op:=s[1];
    win:=id(s[3]);
    delete(s,1,4);
    case op of
      'w':begin
            x1[win]:=getvalue(s);
            y1[win]:=getvalue(s);
            x2[win]:=getvalue(s);
            y2[win]:=getvalue(s);
            if x1[win]>x2[win] then exchange(x1[win],x2[win]);
            if y1[win]>y2[win] then exchange(y1[win],y2[win]);
            inc(top);
            lv[win]:=top;
            exist[win]:=true;
          end;
      't':begin
            inc(top);
            lv[win]:=top;
          end;
      'b':begin
            dec(bottom);
            lv[win]:=bottom;
          end;
      'd':exist[win]:=false;
      's':cal(win);
    end;
  until eof(fin);

  close(fin);
  close(fout);
end.