HDU 1255 覆蓋的面積：掃描線 + 線段樹維護至少兩層覆蓋長度

HDU 1255 覆蓋的面積：掃描線求至少兩層覆蓋面積

給定 n 個矩形，求被至少兩個矩形覆蓋的總面積。坐標為浮點數，需輸出保留兩位小數。

線段樹節點設計

節點存儲：
cnt：區間被完全覆蓋的次數。
len1：區間被覆蓋 ≥1 次的總長度。
len2：區間被覆蓋 ≥2 次的總長度。
維護邏輯（maintain）：
- cnt ≥ 2：len1 = len2 = 區間長度。
- cnt == 1：len1 = 區間長度；len2 = 左子樹.len1 + 右子樹.len1（子樹覆蓋一次，加上本層一次 = 兩次）。
- cnt == 0：len1 = 左.len1 + 右.len1；len2 = 左.len2 + 右.len2。
葉子節點特判。

掃描線流程

矩形邊生成水平掃描線（底邊 tag=+1，頂邊 tag=-1），按 y 排序。x 坐標離散化。遍歷掃描線，更新線段樹，面積增量 = tree[1].len2 * (next_y - cur_y)。

代碼實現

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1010;
double x[maxn*2];
struct Line { double x1, x2, y; int tag; bool operator < (const Line &tmp) const { return y < tmp.y; } } line[maxn*2];
struct node { int l, r, cnt; double len1, len2; } tree[maxn*8];
int Binsearch(int l, int r, double key) {
    int low = l, high = r;
    while (high >= low) {
        int mid = (low + high) >> 1;
        if (x[mid] == key) return mid;
        if (x[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}
void build(int v, int l, int r) {
    tree[v].l = l; tree[v].r = r; tree[v].cnt = 0; tree[v].len1 = tree[v].len2 = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(v*2, l, mid); build(v*2+1, mid+1, r);
}
void maintain(int v) {
    if (tree[v].cnt >= 2) { tree[v].len1 = tree[v].len2 = x[tree[v].r+1] - x[tree[v].l]; return; }
    if (tree[v].cnt == 1) {
        tree[v].len1 = x[tree[v].r+1] - x[tree[v].l];
        if (tree[v].l == tree[v].r) tree[v].len2 = 0;
        else tree[v].len2 = tree[v*2].len1 + tree[v*2+1].len1;
        return;
    }
    if (tree[v].cnt == 0) {
        if (tree[v].l == tree[v].r) tree[v].len1 = tree[v].len2 = 0;
        else { tree[v].len1 = tree[v*2].len1 + tree[v*2+1].len1; tree[v].len2 = tree[v*2].len2 + tree[v*2+1].len2; }
        return;
    }
}
void update(int v, int l, int r, int tag) {
    if (tree[v].l == l && tree[v].r == r) { tree[v].cnt += tag; maintain(v); return; }
    int mid = (tree[v].l + tree[v].r) >> 1;
    if (r <= mid) update(v*2, l, r, tag);
    else if (l > mid) update(v*2+1, l, r, tag);
    else { update(v*2, l, mid, tag); update(v*2+1, mid+1, r, tag); }
    maintain(v);
}
int main() {
    int test, n; double x1, y1, x2, y2; int cnt, k;
    scanf("%d", &test);
    while (test--) {
        scanf("%d", &n); cnt = 0; memset(x, 0, sizeof(x));
        for (int i = 1; i <= n; i++) {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            line[++cnt] = {x1, x2, y1, 1}; x[cnt] = x1;
            line[++cnt] = {x1, x2, y2, -1}; x[cnt] = x2;
        }
        sort(x+1, x+1+cnt); sort(line+1, line+1+cnt);
        k = 1;
        for (int i = 2; i <= cnt; i++) if (x[i] != x[i-1]) x[++k] = x[i];
        build(1, 1, k);
        double ans = 0;
        for (int i = 1; i < cnt; i++) {
            int l = Binsearch(1, k, line[i].x1);
            int r = Binsearch(1, k, line[i].x2) - 1;
            update(1, l, r, line[i].tag);
            ans += (line[i+1].y - line[i].y) * tree[1].len2;
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}

關鍵在 maintain 邏輯正確體現「至少兩層」語義，離散化 + 掃描線 + 線段樹經典組合。