矩形切割例子

衛(wèi)星覆蓋

SERCOI（Space-Earth Resource Cover-Observe lnstitute）是一個致力于利用衛(wèi)星技術對空間和地球資源進行覆蓋觀測的組織。他們研制成功一種新型資源觀測衛(wèi)星-SERCOI-308。這種衛(wèi)星可以覆蓋空間直角坐標系中一定大小的立方體空間，衛(wèi)星處于該立方體的中心。

其中（x,y,z）為立方體的中心點坐標，r為此中心點到立方體各個面的距離（即r為立方體高的一半）．立方體的各條邊均平行于相應的坐標軸。我們可以用一個四元組(x,y,z,r)描述一顆衛(wèi)星的狀態(tài)，它所能覆蓋的空間體積 。

由于一顆衛(wèi)星所能覆蓋的空間體積是有限的，因此空間中可能有若干顆衛(wèi)星協(xié)同工作。它們所覆蓋的空間區(qū)域可能有重疊的地方。

寫一個程序，根據(jù)給定的衛(wèi)星分布情況，計算它們所覆蓋的總體積。

輸入輸出

輸入文件是INPU.TXT。文件的第一行是一個正整數(shù)N（1<=N<=10O）：表示空間中的衛(wèi)星總數(shù)。接下來的N行每行給出了一顆衛(wèi)星的狀態(tài)，用空格隔開的四個正整數(shù)x,y,z,r依次表示了該衛(wèi)星所能覆蓋的立方體空間的中心點坐標和半高，其中-1000<=x,y,z<=1000, 1<=r<=200。

輸出文件是OUTPUT.TXT。文件只有一行,包

括一個正整數(shù)，表示所有這些衛(wèi)星所覆蓋的空間總體積。

樣例

INPUT.TXT

3

0 0 0 3

1 –1 0 1

19 3 5 6

OUTPUT.TXT

1944

這題可以用立方體切割來做，每讀入一個立方體

(x3,y3,z3,x4,y4,z4)，就和已有的立方體(x1,y1,z1,x2,y2,z2)判斷是否有重疊，有的

話就進行切割。所有的數(shù)據(jù)處理完后就可以將全部立方體的體積加起來，就能得

出答案了。

應該注意的是新切割生成的立方體與立方體(x3,y3,z3,x4,y4,z4)是不會有重

疊部分的。因此我們在讀入矩形(x3,y3,z3,x4,y4,z4)之前，先把當前立方體集合中

的立方體總數(shù)tot 記錄起來 tot1 ← tot，那么循環(huán)判斷立方體重疊只需循環(huán)到tot1

就行了，新生成的立方體就無需與立方體(x3,y3,z3,x4,y4,z4)判斷是否重疊了。這

樣可以節(jié)省不少時間。2100433B

procedure cal(l,r,b,t,z:longint);

begin

while (z<=n)and((l>x2[z])or(ry2[z])or(t

if z>n then

begin

inc(col[now],(r-l 1)*(t-b 1));

exit;

end;

if l

begin

cal(l,x1[z]-1,b,t,z 1);

l:=x1[z];

end;

if r>x2[z] then

begin

cal(x2[z] 1,r,b,t,z 1);

r:=x2[z];

end;

if t>y2[z] then

begin

cal(l,r,y2[z] 1,t,z 1);

t:=y2[z];

end;

if b

begin

cal(l,r,b,y1[z]-1,z 1);

b:=y1[z];

end;

end;

procedure work;

var

i,j,k:longint;

begin

x1[0]:=1;

y1[0]:=1;

x2[0]:=a;

y2[0]:=b;

color[0]:=1.0;

for i:=n downto 0 do

begin

now:=color[i];

cal(x1[i],x2[i],y1[i],y2[i],i 1);

end;

for i:=1 to 1000 do

if col[i]>0 then

writeln(i,' ',col[i]);

end;

矩形切割主要解決有重疊部分的面積計算問題。

矩形切割是一種處理平面上矩形的統(tǒng)計的方法。

許多統(tǒng)計類的問題通過數(shù)學建模后都能轉(zhuǎn)化為用矩形切割來解決。矩形切割的原型是線段切割，可以拓展到三維的立方切割。

（1）線段切割

（2）矩形切割

（3）立方切割