线段树的扫描线算法-MuQYY的博客

1. 问题描述

在二维平面上给定若干个矩形，每个矩形由左上角和右下角的坐标确定。目标是计算这些矩形在平面上总的覆盖面积。注意，矩形之间可能存在重叠，我们需要排除重叠部分的重复计算。

为了解决这个问题，我们使用扫描线算法，通过在平面上模拟一条水平移动的扫描线来动态维护被覆盖的区间。

2. 核心思路

事件线生成：
每个矩形的上下边（即 y 轴上的两个边界）视为两个事件：进入事件和离开事件。
- 当扫描线遇到矩形的底边时，它将从覆盖区域中移除该矩形的影响。
- 当扫描线遇到矩形的顶边时，它将增加新的覆盖区域。
线段树维护：
我们用线段树来动态记录和管理哪些区间被覆盖了。具体来说，线段树会存储：
- 被覆盖的 x 区间的总长度。
- 某区间是否被有效覆盖的次数。
面积计算：
当扫描线从一条事件线移动到下一条时，我们计算这段高度的增量面积，并将所有增量面积累加，得到总的覆盖面积。

3. 核心步骤与描述

扫描线事件定义

每条事件线可以表示为：

Event = (y, x_left, x_right, inout)

其中：

y：该边的 y 坐标
x_left 和 x_right：矩形的左右边 x 坐标
inout：进入事件为 1，离开事件为 -1

离散化 x 坐标

收集所有的 x 坐标，并使用 lower_bound 进行离散化，把浮点 x 坐标映射成整数索引，便于线段树操作。

4. 代码示范

数据结构定义

struct ScanLine {
    double y, left_x, right_x;
    int inout;
    ScanLine(double y, double x2, double x1, int io)
        : y(y), left_x(x1), right_x(x2), inout(io) {}
};

ScanLine 用于存储每条扫描线事件的信息。

面积增量计算

在每条扫描线事件之间计算增量面积：

delta_area = covered_length * (y_i - y_(i-1))

5. 线段树的维护

pushup 操作（向上更新）

void pushup(int p, int pl, int pr) {
    if (Tag[p]) {
        length[p] = xx[pr] - xx[pl];  // 区间完全覆盖
    } else if (pl + 1 == pr) {
        length[p] = 0;  // 叶子节点未覆盖
    } else {
        length[p] = length[ls(p)] + length[rs(p)];
    }
}

update 操作（更新线段树）

void update(int L, int R, int io, int p, int pl, int pr) {
    if (L <= pl && pr <= R) {
        Tag[p] += io;  // 更新覆盖标志
        pushup(p, pl, pr);
        return;
    }
    if (pl + 1 == pr) return;  // 到达叶子节点
    int mid = (pl + pr) >> 1;
    if (L <= mid) update(L, R, io, ls(p), pl, mid);
    if (R > mid) update(L, R, io, rs(p), mid, pr);
    pushup(p, pl, pr);
}

6. 主函数流程

int main() {
    int n, t = 0;
    while (scanf("%d", &n), n) {
        int cnt = 0;
        while (n--) {
            double x1, x2, y1, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            line[++cnt] = ScanLine(y1, x2, x1, 1);  // 进入事件
            xx[cnt] = x1;
            line[++cnt] = ScanLine(y2, x2, x1, -1); // 离开事件
            xx[cnt] = x2;
        }
        sort(xx + 1, xx + cnt + 1);
        sort(line + 1, line + cnt + 1, cmp);

        int num = unique(xx + 1, xx + cnt + 1) - (xx + 1);
        memset(Tag, 0, sizeof(Tag));
        memset(length, 0, sizeof(length));

        double ans = 0;
        for (int i = 1; i <= cnt; ++i) {
            ans += length[1] * (line[i].y - line[i - 1].y);  // 面积累加
            int L = lower_bound(xx + 1, xx + num + 1, line[i].left_x) - xx;
            int R = lower_bound(xx + 1, xx + num + 1, line[i].right_x) - xx;
            update(L, R, line[i].inout, 1, 1, num);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n", ++t, ans);
    }
    return 0;
}