計(jì)算幾何切割矩形參考

1、第三題 區(qū)域面積這道題雖然第一反應(yīng)是二維線(xiàn)段樹(shù)，但顯然不必，況且 usaco 內(nèi)存空間只給 16M，空間甚緊。有一種簡(jiǎn)單易寫(xiě)的算法，有人稱(chēng)之為“切割浮水法”。本人當(dāng)初做這題時(shí)并不會(huì)離散化，不過(guò)很幸運(yùn)，自己想到了這種算法，后來(lái)看了 Maigo 大牛的代碼發(fā)現(xiàn)也是這么做的。（1）（2）將矩形0N（底色為 0 號(hào)）。對(duì)于為 i 的矩形，用遞歸方法，一層層上浮，遇到第 j 號(hào)矩形時(shí)，判斷相交的情況（共 17 種），然后分割，繼續(xù)上浮，直到最頂時(shí)計(jì)算面積。相交的 17 種情況如下：（3）點(diǎn)評(píng)：byjt第三題 區(qū)域面積區(qū)域面積是做 usaco 的選手最容易被“卡殼”的題目之一，多數(shù)同學(xué)都因?yàn)槌瑫r(shí)而不能通過(guò)

2、。但有意思的是，本題可通過(guò)的方法有好幾種，思路也大相徑庭。最常用的方法有兩種：1、 先離散化，再對(duì)每一“行”進(jìn)行用線(xiàn)段樹(shù)來(lái)加快處理。2、 矩形切割法。另外，處理矩形的前后次序也有兩種：按讀入的（放置）次序，從下向上處理?；蛳喾?，先處理最上面的矩形，再處理它下面的。上面試題分析中的方法就屬于第二類(lèi)：切割法。但是分析中的 17 種切割方案讓人佩服之余也有點(diǎn)擔(dān)心，在緊張的比賽當(dāng)場(chǎng)，不遺漏地分析出 17 種方案難度很大。能否合并一些情況呢？首先來(lái)看一下分割最多的情況：大的矩形被“切割”成 4 個(gè)小的矩形A、B、C、D。如果把中間的矩形不斷向上移動(dòng)，最終會(huì)出現(xiàn)上面分析中的另一種分割方案：如果把的 A 區(qū)

3、域看成是一個(gè)上面情況的“負(fù)”矩形，則上面兩種情況是的。類(lèi)似分析，上文中的 17 種分割方案的前 16 種方案其實(shí)可以成一種情況！主要過(guò)程簡(jiǎn)化為：void swim(x1,y1,x2,y2,cl,lv )if( x1 = x2 | y1 = y2 )/負(fù)矩形 return;if( lv = N + 1 )Area cl += ( x2 - x1 ) * ( y2 - y1 ); return;else if( cut17( x1, y1, x2, y2, lv ) ) swim( x1, y1, x2, y2, cl, lv + 1 );elseBCDABCDswim( x1, y1, x2,

4、rect lv .y1, cl, lv + 1 ); /A 區(qū)域swim( x1, max(rect lv .y1,y1), rect lv .x1, min(rect lv .y2,y2), cl, lv + 1 );/Bswim( rect lv .x2, max(rect lv .y1,y1), x2, min(rect lv .y2,y2), cl, lv + 1 );/C swim( x1, rect lv .y2, x2, y2, cl, lv + 1 ); / Dinline bool cut17(x1,y1,x2,y2,stopRect )if( rect stopRect .x1 =x2 | rect stop