扫描线与线段树几何应用

📖 算法原理：维度切割与线段树高度更新

扫描线算法（Sweep-Line Algorithm）是计算几何中的经典策略，常用于求解重叠矩形面积并（Union of Rectangles）等空间覆盖问题。

📐 扫描线求面积并核心理论

对于画布上若干可能相互重叠的矩形，我们很难直接根据加减公式扣除重叠部分的面积：

X 轴切片化：将每个矩形的左边界和右边界看作“事件（Events）”。左边界为入边事件（高度累加，值 $+1$）；右边界为出边事件（高度移除，值 $-1$）。
自左向右扫掠：将所有事件按 $X$ 坐标升序排列。一根垂直的黄金扫描线从左向右依次划过各事件。
高度的线段树维护：
- 扫描线在相邻两次事件之间划过的距离为 $\Delta X = X_i - X_{i-1}$。
- 在此 $\Delta X$ 区间内，扫描线截得的重叠矩形有效总高度（Union Length）是恒定不变的。
- 我们利用线段树（Segment Tree）维护纵坐标 $Y$ 区间的覆盖次数。入边事件在对应 $Y$ 区间执行 $+1$；出边在对应 $Y$ 范围执行 $-1$。线段树根节点的 tree[1].len 实时返回当前被覆盖的总有效高度。
累加求和：每步累加切片面积 $\Delta S = \Delta X \times \text{tree}[1].len$。最终得出完美的总覆盖面积！

当前区间宽度 $\Delta X$

线段树有效高度 $H_{active}$

累计覆盖总面积 $\text{Total Area}$

扫掠速度：

点击“开始扫描线扫掠”或“单步事件”，观察黄色扫描线移动、绿色高度更新及线段树的状态变化。

🗺️ 2D 矩形几何空间与扫描线 (Rectangle Space & Sweep-Line)

🌲 纵向 Y 区间线段树维护状态 (Y-Interval Segment Tree)

struct SegTree {
    int l, r;
    int cnt;     // 该区间被完整覆盖的次数
    double len;  // 该区间内被覆盖的有效高度
} tree[MAXN << 3];

// 扫描线事件结构体
struct Event {
    double x;
    double y1, y2;
    int k; // +1 入边，-1 出边
    bool operator<(const Event& t) const {
        return x < t.x;
    }
} events[MAXN << 1];

// 线段树核心高度推导更新
void pushup(int u) {
    if (tree[u].cnt > 0) {
        // 若被完整覆盖过，有效长度直接为当前区间的离散高度差
        tree[u].len = y[tree[u].r + 1] - y[tree[u].l];
    } else {
        // 若无覆盖，由左右子节点高度和拼装
        tree[u].len = tree[u << 1].len + tree[u << 1 | 1].len;
    }
}

📋 扫描线切片积分记录