USACO 5.3.2 Window Area[模拟+矩阵切割]_¢Innocence、_百度空间
超级{wd}打字题153行....开两个指针记录头尾,每个窗口记录前驱后继,再开个数组记录各个窗口名称所对位置。模拟操作....矩阵切割求答案
{
ID:sedream1
PROG:window
LANG:PASCAL
}
type rey=record
           x1,y1,x2,y2,pre,next:longint;
         end;
var d:array[1..2000]of rey;
    st:string;
    x1,y1,x2,y2,tot,head,tail,s,t,p,q,temp:longint;
    po:array['0'..'z']of longint;
    id,ch:char;
procedure get(t,x1,y1,x2,y2:longint);
begin
    if t=0 then begin inc(s,(x2-x1)*(y2-y1));exit;end;
    if (d[t].x1>x2)or(d[t].x2<x1)or(d[t].y1>y2)or(d[t].y2<y1)then
      begin get(d[t].pre,x1,y1,x2,y2);exit;end;
    if d[t].x1>x1 then begin get(d[t].pre,x1,y1,d[t].x1,y2);x1:=d[t].x1;end;
    if d[t].x2<x2 then begin get(d[t].pre,d[t].x2,y1,x2,y2);x2:=d[t].x2;end;
    if d[t].y1>y1 then get(d[t].pre,x1,y1,x2,d[t].y1);
    if d[t].y2<y2 then get(d[t].pre,x1,d[t].y2,x2,y2);
end;
procedure deal_w(st:string);
begin
    id:=st[1];
    delete(st,1,2);
    x1:=0;
    while st[1]<>',' do
      begin
        x1:=x1*10+ord(st[1])-48;
        delete(st,1,1);
      end;
    delete(st,1,1);
    y1:=0;
    while st[1]<>',' do
      begin
        y1:=y1*10+ord(st[1])-48;
        delete(st,1,1);
      end;
    delete(st,1,1);
    x2:=0;
    while st[1]<>',' do
      begin
        x2:=x2*10+ord(st[1])-48;
        delete(st,1,1);
      end;
    delete(st,1,1);
    y2:=0;
    while st[1]<>')' do
      begin
        y2:=y2*10+ord(st[1])-48;
        delete(st,1,1);
      end;
    if x1>x2 then
      begin
        temp:=x1;x1:=x2;x2:=temp;
      end;
    if y1>y2 then
      begin
        temp:=y1;y1:=y2;y2:=temp;
      end;
end;
begin
assign(input,'window.in');reset(input);
assign(output,'window.out');rewrite(output);
tot:=0;
repeat
    readln(st);
    ch:=st[1];
    delete(st,1,2);
    case ch of
      'w':begin
            deal_w(st);
            inc(tot);
            d[tot].x1:=x1;d[tot].y1:=y1;d[tot].x2:=x2;d[tot].y2:=y2;
            if tail<>0 then
              begin
                d[tot].next:=head;
                d[head].pre:=tot;
              end else tail:=tot;
            head:=tot;d[tot].pre:=0;
            po[id]:=tot;
          end;
      't':begin
            id:=st[1];
            t:=po[id];
            p:=d[t].pre;q:=d[t].next;
            if (p<>0) then
              begin
                if q<>0 then
                  begin
                    d[p].next:=q;d[q].pre:=p;
                  end else
                  begin
                    d[p].next:=0;tail:=p;
                  end;
                d[t].next:=head;d[head].pre:=t;
                head:=t;d[t].pre:=0;
              end;
          end;
      'b':begin
            id:=st[1];
            t:=po[id];
            p:=d[t].pre;q:=d[t].next;
            if q<>0 then
              begin
                if p<>0 then
                  begin
                    d[p].next:=q;d[q].pre:=p;
                  end else
                  begin
                    d[q].pre:=0;head:=q;
                  end;
                d[tail].next:=t;d[t].pre:=tail;
                tail:=t;d[t].next:=0;
              end;
          end;
      'd':begin
            id:=st[1];
            t:=po[id];
            p:=d[t].pre;q:=d[t].next;
            if p<>0 then
              begin
                if q<>0 then
                  begin
                    d[p].next:=q;d[q].pre:=p;
                  end else
                  begin
                    d[p].next:=0;tail:=p;
                  end;
              end else
              begin
                if q<>0 then
                  begin
                    d[q].pre:=0;head:=q;
                  end else
                  begin
                    head:=0;tail:=0;
                  end;
              end;
          end;
      's':begin
            id:=st[1];
            t:=po[id];
            s:=0;
            get(d[t].pre,d[t].x1,d[t].y1,d[t].x2,d[t].y2);
            writeln(s/(d[t].x2-d[t].x1)/(d[t].y2-d[t].y1)*100:0:3);
          end;
    end;
until eof;
close(input);close(output);
end.


郑重声明:资讯 【USACO 5.3.2 Window Area[模拟+矩阵切割]_¢Innocence、_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——