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