USACO Window AreaDFS矩形切割

对每个矩形都存一个优先值,如果一个矩形被放到上面,则它的优先级变为当前的最大+1,放到下面就是当前最小-1,被删除则是-maxlongint。接着我们只要考虑所有优先级比它大的矩形就行了。

这道题的难点就是如何得到一块矩形在被优先值比它大的矩形覆盖之后的矩形。使用DFS实现分治。如果矩形i被矩形j切割,则我们把切割留下来的部分以几个小矩形的形式存下来,分别给别的矩形切割,切割的时候分上下左右四个方向判断即可。具体请看程序。

{
ID:htx_2006
PROB:window
LANG:PASCAL
}
const
mm=10+26+26;
type
ltype=record
          num,x1,y1,x2,y2:longint;
        end;
var
i,j,k,l,m,n,tot1,tot2,now,sum:longint;
a,a1:array[0..100]of ltype;
b,cc:array[1..100]of longint;
temp:integer;
op,ch,ch2,c:char;
s:string;
w:array[0..4]of longint;
function zemin(c:char):longint;
begin
if (c>='0')and(c<='9') then exit(ord(c)-47);
if (c>='a')and(c<='z') then exit(ord(c)-96+10);
exit(ord(c)-64+10+26);
end;
function cal(x1,y1,x2,y2,st:longint):longint;
var
sum:longint;
begin
while (st>0)and((x2<a1[st].x1)or(x1>a1[st].x2)or(y2>a1[st].y1)or(y1<a1[st].y2)) do
    dec(st);
if st=0 then exit((x2-x1)*(y1-y2));
sum:=0;
if a1[st].x1>x1 then
    begin
      sum:=sum+cal(x1,y1,a1[st].x1,y2,st-1);
      x1:=a1[st].x1;
    end;
if a1[st].x2<x2 then
    begin
      sum:=sum+cal(a1[st].x2,y1,x2,y2,st-1);
      x2:=a1[st].x2;
    end;
if a1[st].y1<y1 then
    begin
      sum:=sum+cal(x1,y1,x2,a1[st].y1,st-1);
      y1:=a1[st].y1;
    end;
if a1[st].y2>y2 then
    begin
      sum:=sum+cal(x1,a1[st].y2,x2,y2,st-1);
      y2:=a1[st].y2;
    end;
cal:=sum;
end;
procedure qsort(l,r:longint);
var
i,j,x:longint;
begin
i:=l; j:=r; x:=a1[(l+r) div 2].num;
repeat
    while a1[i].num<x do inc(i);
    while a1[j].num>x do dec(j);
    if i<=j then
    begin
      a1[0]:=a1[i]; a1[i]:=a1[j]; a1[j]:=a1[0];
      k:=b[i]; b[i]:=b[j]; b[j]:=k;
      inc(i); dec(j);
    end;
until i>j;
if j>l then qsort(l,j);
if i<r then qsort(i,r);
end;
function min(a,b:longint):longint;
begin
min:=a;
if b<a then exit(b);
end;
function max(a,b:longint):longint;
begin
max:=a;
if b>a then exit(b);
end;
begin
assign(input,'window.in');reset(input);
assign(output,'window.out');rewrite(output);
tot1:=0; tot2:=0;
fillchar(a,sizeof(a),0);
for i:=1 to mm do a[i].num:=20000;
while not eof do
    begin
      read(op,ch2,ch);
      now:=zemin(ch);
      if op='w' then
      begin
        m:=0;
        while not eoln do
          begin
            read(c);
            if (c=',')or(c=')') then
            begin
              val(s,w[m],temp); inc(m);
              s:=''; continue;
            end;
            s:=s+c;
          end;
        dec(tot1);
        a[now].num:=tot1;
        a[now].x1:=min(w[1],w[3]); a[now].y1:=max(w[2],w[4]);
        a[now].x2:=max(w[1],w[3]); a[now].y2:=min(w[2],w[4]);
      end else
      if op='d' then a[now].num:=20000 else
      if op='t' then begin dec(tot1); a[now].num:=tot1; end else
      if op='b' then begin inc(tot2); a[now].num:=tot2; end else
      if op='s' then
      begin
        a1:=a;
        for i:=1 to mm do b[i]:=i;
        qsort(1,mm);
        for i:=1 to mm do cc[b[i]]:=i;
        sum:=cal(a[now].x1,a[now].y1,a[now].x2,a[now].y2,cc[now]-1);
        writeln(sum/((a[now].x2-a[now].x1)*(a[now].y1-a[now].y2))*100:0:3);
      end;
      readln;
    end;
close(input);close(output);
end.

原文地址:https://www.cnblogs.com/nbalive2001/p/2597429.html