首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

HDU 1828 / POJ 1177 Picture:掃描線+線段樹+離散化求矩形周長

     編輯:C++ 入門

題目核心

給定 N 個矩形,求它們聯集的周長。N ≤ 5000,坐標範圍需離散化。

算法思路:雙向掃描累加邊長變化

周長 = 水平邊長總和 + 豎直邊長總和。兩者對稱,只需掃描兩次。

水平邊掃描(橫向)

  • 將每個矩形拆為兩條水平掃描線:
    • 底邊 y1:cover = +1,區間 [x1, x2)
    • 頂邊 y2:cover = -1,區間 [x1, x2)
  • 按 y 排序掃描線
  • 線段樹維護當前 x 方向的總覆蓋長度 len
  • 相鄰兩條掃描線之間,水平邊長貢獻 = |len[i] - len[i-1]|

豎直邊掃描(縱向)

將 x, y 互換,重複上述過程,累加豎直邊長變化。

關鍵數據結構

struct Edge { int l, r, h, f; };  // l,r: x區間; h: 掃描線座標; f: +1/-1
int c[MAXN];       // 離散化坐標數組
int cover[4*MAXN]; // 線段樹覆蓋計數
int len[4*MAXN];   // 線段樹維護的覆蓋長度
int lazy[4*MAXN];  // 延遲標記

線段樹 PushUp 邏輯

void PushUp(int rt, int l, int r) {
    if (lazy[rt]) 
        sum[rt] = c[r+1] - c[l];  // 完全覆蓋,長度 = 離散化座標差
    else if (l == r)
        sum[rt] = 0;              // 葉節點無覆蓋
    else
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];  // 合併子節點
}

完整流程

  1. 讀入矩形,收集所有 x 坐標離散化
  2. 構建水平掃描線,排序,線段樹掃描累加 ans += |len - last|
  3. 清空數據結構,收集所有 y 坐標離散化
  4. 構建豎直掃描線(x↔y),再次掃描累加
  5. 輸出總周長 ans

複雜度

  • 時間:O(N log N)(排序 + 2N 次線段樹更新)
  • 空間:O(N)

代碼亮點

  • 二分查找 erfen() 映射離散化索引
  • 線段樹區間更新傳遞 f(+1/-1)而非布爾值,支援多層覆蓋
  • 離散化數組 c[] 留出 c[r+1] 邊界,避免越界
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved