矩形面积并问题题解（线段树实现）

题目理解

本题要求计算多个矩形在平面上的总面积并（即所有矩形覆盖区域的总面积，重叠部分只计算一次）。使用扫描线算法结合线段树实现高效计算。

算法思路

关键步骤

1. 离散化处理：将y坐标排序并去重
2. 扫描线算法：沿x轴方向扫描，将矩形拆分为左右两条边
3. 线段树维护：动态统计当前x位置的有效y区间长度

数学表达

• 总面积并公式：$$Area = \sum_{i=1}^{n} (x_{i+1}-x_i) \times L_{valid} $$其中$L_{valid}$为x区间$[x_i,x_{i+1}]$内有效的y轴长度

代码解析

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn = 110;

struct LINE {
    double x, y_down, y_up;
    int flag; // 1表示矩形左边，-1表示右边
    bool operator<(const LINE &a) const {
        return x < a.x; // 按x坐标排序
    }
} line[2*maxn];

struct TREE {
    double x, y_down, y_up;
    int cover; // 当前区间被覆盖次数
    bool flag; // 是否为叶子节点
} tree[1000*maxn];

double y[2*maxn]; // 存储所有y坐标用于离散化

void build(int i, int l, int r) {
    tree[i].x = -1;
    tree[i].cover = 0;
    tree[i].y_down = y[l];
    tree[i].y_up = y[r];
    tree[i].flag = false;
    
    if(l+1 == r) {
        tree[i].flag = true; // 标记叶子节点
        return;
    }
    
    int mid = (l+r)>>1;
    build(2*i, l, mid);
    build(2*i+1, mid, r);
}

double insert(int i, double x, double l, double r, int flag) {
    // 当前区间与查询区间无交集
    if(r <= tree[i].y_down || l >= tree[i].y_up) 
        return 0;
    
    // 叶子节点处理
    if(tree[i].flag) {
        if(tree[i].cover > 0) { // 存在覆盖则计算面积
            double temp_x = tree[i].x;
            double ans = (x-temp_x)*(tree[i].y_up-tree[i].y_down);
            tree[i].cover += flag;
            tree[i].x = x;
            return ans;
        } else { // 更新覆盖状态
            tree[i].cover += flag;
            tree[i].x = x;
            return 0;
        }
    }
    
    // 非叶子节点递归处理
    return insert(2*i, x, l, r, flag) + insert(2*i+1, x, l, r, flag);
}

int main() {
    int Case = 0, n, index;
    double x1, y1, x2, y2;
    
    while(~scanf("%d", &n) && n) {
        index = 1;
        // 输入处理
        for(int i=1; i<=n; i++) {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            y[index] = y1;
            line[index] = {x1, y1, y2, 1}; // 左边
            index++;
            
            y[index] = y2;
            line[index] = {x2, y1, y2, -1}; // 右边
            index++;
        }
        
        // 离散化处理
        sort(y+1, y+index);
        sort(line+1, line+index);
        
        // 建树
        build(1, 1, index-1);
        
        // 扫描线处理
        double ans = 0;
        for(int i=1; i<index; i++) {
            ans += insert(1, line[i].x, line[i].y_down, 
                         line[i].y_up, line[i].flag);
        }
        
        printf("Test case #%d\nTotal explored area: %.2f\n\n", 
              ++Case, ans);
    }
    return 0;
}

复杂度分析

• 时间复杂度：

  • 排序：$O(n\log n)$
  • 线段树操作：$O(n\log n)$
  • 总体：$O(n\log n)$

• 空间复杂度：

  • 线段树：$O(n)$
  • 辅助数组：$O(n)$

关键点说明

1. 离散化处理：

   • 对所有y坐标排序去重
   • 建立线段树时使用离散化后的y坐标

2. 扫描线算法：

   • 将每个矩形拆分为左右两条边
   • 按x坐标排序后从左到右扫描

3. 线段树设计：

   • $cover$记录区间被覆盖次数
   • $flag$标记叶子节点
   • 面积计算只在叶子节点进行

数学表达补充

1. 区间覆盖计算：

   $$L_{valid} = \sum_{i} (y_{i+1}-y_i) \times \mathbb{I}(cover_i > 0) $$

   其中$\mathbb{I}$为指示函数

2. 面积积分思想：

   $$Area = \int_{x_{min}}^{x_{max}} L_{valid}(x) \,dx $$

注意事项

1. 边界处理：

   • 线段树建树时区间为$[l, r)$形式
   • 注意y坐标比较时的开闭区间

2. 精度问题：

   • 使用$double$类型存储坐标和面积
   • 输出保留两位小数

3. 测试格式：

   • 每个测试用例后输出空行
   • 包括测试用例编号

扩展思考

1. 三维情况：

   • 可使用二维线段树处理立方体体积并问题

2. 其他应用：

   • 可扩展计算矩形周长并
   • 可处理多边形面积并问题

该解法充分利用了线段树的高效区间查询特性，结合扫描线算法将二维问题转化为一维问题，达到了$O(n\log n)$的优秀时间复杂度。