Posted on 2011-12-25 16:10
Mato_No1 閱讀(399)
評(píng)論(0) 編輯 收藏 引用
【本沙茶以前曾經(jīng)搞過(guò)
矩形的面積并、周長(zhǎng)并問(wèn)題，當(dāng)時(shí)幾乎是抄神犇代碼的，根本木有理解，現(xiàn)在在看了掃描線以后理解一些了】
“掃描線”嚴(yán)格來(lái)說(shuō)不是算法，而是一種思想，它在解決很多幾何問(wèn)題或者矩陣問(wèn)題中有大用。所謂“掃描線”，就是用一條假想的直線（一般是水平或者豎直的）沿x軸（或y軸）方向掃過(guò)整個(gè)平面，在此過(guò)程中，每當(dāng)發(fā)現(xiàn)有特殊事件（比如插入、刪除事件等），就執(zhí)行這一事件。一般來(lái)說(shuō)，它需要配合數(shù)據(jù)結(jié)構(gòu)進(jìn)行加速，常用的數(shù)據(jù)結(jié)構(gòu)有線段樹(shù)、平衡樹(shù)、樹(shù)狀數(shù)組、堆、凸多邊形集合等。
【1】矩形的面積并和周長(zhǎng)并問(wèn)題：
這個(gè)在以前總結(jié)的那一篇里面曾經(jīng)說(shuō)明過(guò)，這里只是補(bǔ)充一下。
對(duì)于面積并，可以假想一條水平直線沿y軸正方向掃過(guò)整個(gè)平面，每當(dāng)遇到矩形的上下邊界，就插入或刪除一條線段（上邊界為插入，下邊界為刪除），在每?jī)蓚€(gè)相鄰上下邊界之間得到覆蓋面積為：目前插入（尚未刪除）的所有線段覆蓋的總長(zhǎng)度乘以兩邊界間的距離。顯然，求前者需要用離散化（橫坐標(biāo)）+線段樹(shù)實(shí)現(xiàn)。
這里講一下離散化的步驟和易疵點(diǎn)：首先將要離散化的數(shù)據(jù)（設(shè)為A數(shù)組）存儲(chǔ)在一個(gè)數(shù)組B里，然后對(duì)B排序（一般是遞增排序）、去重（方法：
若B長(zhǎng)度為0則不需去重，否則B[0]保留，從B[1]開(kāi)始，若B[i]>B[i-1]則保留B[i]否則跳過(guò)B[i]），得到一個(gè)新的數(shù)組B0，最后，再對(duì)原來(lái)的A數(shù)組中的每個(gè)元素在B0中二分查找，找到其位置即可。顯然，對(duì)N個(gè)數(shù)據(jù)離散化時(shí)間復(fù)雜度為O(NlogN)，具體實(shí)現(xiàn)時(shí)，可不設(shè)B0，直接存在B里面（見(jiàn)代碼）。易疵的地方主要是B的長(zhǎng)度為0的情況。
re(i, n0) B[i] = A[i].x;
qsort(B, n0, sizeof(B[0]), cmp);
n = 1; re2(i, 1, n0) if (B[i] > B[i - 1]) B[n++] = B[i];
re(i, n0) A[i].x = find_x(A[i].x);
其中n0為數(shù)據(jù)個(gè)數(shù)，n為去重后的數(shù)據(jù)個(gè)數(shù)（也就是離散化后的編號(hào)范圍，很重要的！），find_x為二分查找過(guò)程。
對(duì)于周長(zhǎng)并可以這樣理解：照樣是水平直線沿y軸正方向掃過(guò)整個(gè)平面，照樣是遇到矩形的上下邊界就插入或刪除，這樣，周長(zhǎng)的水平部分是很好得到的，只要統(tǒng)計(jì)每?jī)蓚€(gè)相鄰上下邊界的線段覆蓋總長(zhǎng)之差即可，對(duì)于豎直部分則需要統(tǒng)計(jì)被
線段覆蓋的端點(diǎn)個(gè)數(shù)——或者說(shuō)，需要統(tǒng)計(jì)至少作為一條目前插入線段的端點(diǎn)，且木有被任何一條線段內(nèi)部包含的端點(diǎn)個(gè)數(shù)（因?yàn)橹挥羞@些點(diǎn)所延伸下來(lái)的豎直線段有可能作為周長(zhǎng)的豎直部分）。維護(hù)方法：給每個(gè)結(jié)點(diǎn)設(shè)立ss、lbd與rbd，分別表示該結(jié)點(diǎn)區(qū)間內(nèi)這種點(diǎn)的個(gè)數(shù)，以及該線段區(qū)間的左右端點(diǎn)是不是這種點(diǎn)。lbd=LCH.lbd; rbd=RCH.rbd; ss=LCH.ss+RCH.ss-2*(LCH.rbd || RCH.lbd)（因?yàn)槲覀冃枰氖蔷€段樹(shù)而不是點(diǎn)樹(shù)，因此其中的每個(gè)葉結(jié)點(diǎn)表示的實(shí)際上是一條單位線段，而不是一個(gè)點(diǎn)，這樣，LCH區(qū)間的右端點(diǎn)與RCH區(qū)間的左端點(diǎn)其實(shí)是同一個(gè)點(diǎn)，如果它們都是這種點(diǎn)，則都不能算，因?yàn)楸话趦?nèi)部了）。例外的是，如果某個(gè)結(jié)點(diǎn)區(qū)間完全被某條插入線段包含，則ss為2，lbd、rbd均為1（這個(gè)結(jié)果可能不正確，因?yàn)榭赡茏笥叶它c(diǎn)被包含在內(nèi)部，因此，整棵樹(shù)上只有根結(jié)點(diǎn)的ss值是絕對(duì)正確的ss值，其余結(jié)點(diǎn)都需要特判）。這樣，根結(jié)點(diǎn)的ss值就是這種點(diǎn)的個(gè)數(shù)，乘以兩相鄰上下邊界的距離就是之間的豎直部分總長(zhǎng)度。
代碼：
面積并（HDU1542）周長(zhǎng)并（HDU1828）（此外，周長(zhǎng)并還有一種更容易理解的算法：就是先求出水平部分總長(zhǎng)后，將所有的矩形旋轉(zhuǎn)90度，再求一次水平部分總長(zhǎng)，這就是原來(lái)的豎直部分總長(zhǎng)了）
【2】應(yīng)用：
PKU2482