C++ 计算重叠矩形组成的图形面积

给定 N 个平行于坐标轴的矩形，这些矩形可能存在重叠部分，求它们组成的图形的面积。

问题描述

桌面上放了 N 个平行于坐标轴的矩形，这 N 个矩形可能有互相覆盖的部分，求它们组成的图形的面积。

输入格式

输入第一行为一个数 N（1≤N≤100），表示矩形的数量。下面 N 行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为–10^8 到 10^8 之间的整数。

输出格式

输出只有一行，一个整数，表示图形的面积。

样例输入

3
1 1 4 3
2 -1 3 2
4 0 5 2

样例输出

10

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Rectangle {
int x1, y1, x2, y2;
};
int main() {
int N;
cin >> N;
vector&lt;Rectangle&gt; rectangles(N);
for (int i = 0; i &lt; N; i++) {
    cin &gt;&gt; rectangles[i].x1 &gt;&gt; rectangles[i].y1 &gt;&gt; rectangles[i].x2 &gt;&gt; rectangles[i].y2;
}

int totalArea = 0;
for (int i = 0; i &lt; N; i++) {
    totalArea += (rectangles[i].x2 - rectangles[i].x1) * (rectangles[i].y2 - rectangles[i].y1);
    for (int j = i + 1; j &lt; N; j++) {
        int overlapWidth = max(0, min(rectangles[i].x2, rectangles[j].x2) - max(rectangles[i].x1, rectangles[j].x1));
        int overlapHeight = max(0, min(rectangles[i].y2, rectangles[j].y2) - max(rectangles[i].y1, rectangles[j].y1));
        totalArea -= overlapWidth * overlapHeight;
    }
}

cout &lt;&lt; totalArea &lt;&lt; endl;

return 0;

}

代码解析

代码的核心思想是：先计算所有矩形的面积之和，然后减去所有重叠部分的面积。代码中使用了两个循环来遍历所有矩形，计算重叠部分的面积，并将其从总面积中减去。

具体来说，代码中使用 Rectangle 结构体来表示每个矩形，结构体中包含矩形的左下角坐标 (x1, y1) 和右上角坐标 (x2, y2)。

外层循环遍历所有矩形，内层循环遍历当前矩形之后的矩形，计算两个矩形之间的重叠部分面积。重叠部分的宽度和高度分别计算为两个矩形 x 坐标和 y 坐标的最小值和最大值的差值。如果重叠部分的宽度或高度为负数，则说明两个矩形没有重叠，则将其设置为 0。

最后，将所有矩形面积之和减去所有重叠部分面积，即为最终的图形面积。

总结

本篇文章详细讲解了如何使用 C++ 语言计算多个重叠矩形组成的图形面积，并提供了完整的代码实现。文章以清晰的步骤、简洁的代码和丰富的示例，帮助您理解算法原理，并能够独立完成类似问题的解决。