HDU 1542 面積并：掃描線 + 線段樹計算矩形聯覆蓋面積

題目大意

給定 n 個矩形，求它們覆蓋的總面積，重疊區域只計算一次。

掃描線算法流程

1. 離散化：收集所有矩形的 x 坐標，排序去重，映射到索引。
2. 事件構建：每個矩形產生兩條掃描線——底邊（+1）和頂邊（-1），記錄 l, r, h, type。
3. 排序：按 h 從小到大排序掃描線。
4. 線段樹維護：掃描過程中維護當前活躍區間的總覆蓋長度。節點存儲 cover（覆蓋次數）與 len（實際覆蓋長度）。
5. 面積累加：相鄰兩條掃描線高度差 Δh 乘以當前覆蓋長度 len，累加到答案。

線段樹關鍵操作

struct Node {
    int cover;   // 完全覆蓋次數
    double len;  // 該區間實際覆蓋長度
} tree[MAXN * 4];

void push_up(int rt, int l, int r) {
    if (tree[rt].cover > 0) {
        tree[rt].len = X[r + 1] - X[l]; // 完全覆蓋，長度為離散坐標差
    } else if (l == r) {
        tree[rt].len = 0;               // 葉節點無覆蓋
    } else {
        tree[rt].len = tree[rt<<1].len + tree[rt<<1|1].len; // 向子節點詢問
    }
}

void update(int rt, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) {
        tree[rt].cover += val;
        push_up(rt, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) update(rt<<1, l, mid, L, R, val);
    if (R > mid) update(rt<<1|1, mid+1, r, L, R, val);
    push_up(rt, l, r);
}

完整主流程

int main() {
    int n, caseNo = 1;
    while (cin >> n && n) {
        vector<Edge> edges;
        vector<double> xs;
        for (int i = 0; i < n; ++i) {
            double x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            xs.push_back(x1); xs.push_back(x2);
            edges.push_back({x1, x2, y1, 1});
            edges.push_back({x1, x2, y2, -1});
        }
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        // 映射邊的 l, r 到離散索引
        for (auto &e : edges) {
            e.l = lower_bound(xs.begin(), xs.end(), e.l) - xs.begin();
            e.r = lower_bound(xs.begin(), xs.end(), e.r) - xs.begin() - 1;
        }
        sort(edges.begin(), edges.end(), [](auto &a, auto &b){ return a.h < b.h; });
        double area = 0;
        for (int i = 0; i + 1 < edges.size(); ++i) {
            update(1, 0, xs.size()-2, edges[i].l, edges[i].r, edges[i].type);
            area += tree[1].len * (edges[i+1].h - edges[i].h);
        }
        cout << "Test case #" << caseNo++ << "\nTotal explored area: " << fixed << setprecision(2) << area << "\n\n";
    }
}

複雜度

離散化 O(n log n)，掃描線排序 O(n log n)，線段樹每次更新 O(log n)，總時間 O(n log n)，空間 O(n)。