Posted on 2011-07-02 11:17
Mato_No1 閱讀(2763)
評論(0) 編輯 收藏 引用 所屬分類:
線段樹
矩形的面積并問題：平面上有N個矩形，各邊均平行于坐標(biāo)軸，求它們覆蓋的總面積（重復(fù)覆蓋的只計一次）。
矩形的周長并問題：平面上有N個矩形，各邊均平行于坐標(biāo)軸，求它們覆蓋形成的多邊形的周長。
【算法】
面積并：
先將所有矩形的上邊界和下邊界作為水平線段記錄下來，并對所有矩形的左右邊界對應(yīng)的橫坐標(biāo)離散化，設(shè)離散化后有N個橫坐標(biāo)，則中間有(N-1)段。對這(N-1)段建立線段樹（注意，仍然和普通線段樹一樣，是雙閉區(qū)間，不是網(wǎng)上說的一開一閉），然后，按照縱坐標(biāo)遞增順序掃描前面記錄的水平線段（設(shè)有M段），對每一段，如果是上邊界，找到其離散化后的范圍（只需找到其左右端點離散化后的值l、r，則對應(yīng)范圍為[l, r-1]），并插入線段[l, r-1]，否則（下邊界），刪除線段[l, r-1]。再然后，線段樹中的每個結(jié)點需要記錄該區(qū)間內(nèi)的線段覆蓋的總長度len（若該區(qū)間被某條尚未刪除的線段整體覆蓋，則len=總長，否則len=左右子結(jié)點len之和），每次操作后，累加面積：T[root].len*該水平線段與下一條水平線段的縱坐標(biāo)之差。
周長并：
類似，只不過由于組成周長的線段有水平的也有豎直的，線段樹結(jié)點要記錄的除了len意外還有一個ss，表示被線段覆蓋的端點數(shù)量。另外還有l(wèi)r和rr兩個bool值，分別表示該線段的左端點和右端點是否被某條插入的線段覆蓋。則T[x].ss = lch(T[x]).ss + rch(T[x]).ss - 2 * (lch(T[x]).rr && rch(T[x].lr))，若該線段被整體覆蓋則T[x].ss=2（兩端點）。最后，這次得到的T[root].len與上次得到的T[root].len之差的絕對值就是水平線段的長度，T[root].ss*縱坐標(biāo)之差就是豎直線段的長度。