【题目来源】
洛谷：[P1884 USACO12FEB] Overplanting S - 洛谷
【题目描述】
在一个笛卡尔平面坐标系里（则 \(X\) 轴向右是正方向，\(Y\) 轴向上是正方向），有 \(N(1\le N\le 1000)\) 个矩形，第 \(i\) 个矩形的左上角坐标是 \((x_1,y_1)\)，右下角坐标是 \((x_2,y_2)\)。问这 \(N\) 个矩形所覆盖的面积是多少？
注意：被重复覆盖的区域的面积只算一次。
【输入】
第一行，一个整数 \(N(1\le N\le 1000)\)。
接下来有 \(N\) 行，每行描述一个矩形的信息，分别是矩形的 \(x_1,y_1,x_2,y_2(-10^8\le x_1,y_1,x_2,y_2,\le 10^8)\)。
【输出】
一个整数，被 \(N\) 个矩形覆盖的区域的面积。
【输入样例】
2
0 5 4 1
2 4 6 2
【输出样例】
20
【解题思路】
【算法标签】
《洛谷 P1884 Overplanting》 #离散化# #USACO# #2012#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 定义int为long long类型// 矩形结构体，存储对角线坐标
struct Node
{int x1, y1, x2, y2;
} rect[1005]; // 存储所有矩形int n, a[2005], b[2005], ans; // n: 矩形数量，a/b: 坐标离散化数组，ans: 面积结果
bool c[2005][2005]; // 标记矩阵，记录每个小格子是否被覆盖signed main()
{// 输入矩形数量cin >> n;// 输入每个矩形的坐标并存入离散化数组for (int i = 0; i < n; i++) {// 注意输入顺序是y1,x2,y2,x1cin >> rect[i].y1 >> rect[i].x2 >> rect[i].y2 >> rect[i].x1;a[i * 2] = rect[i].x1;a[i * 2 + 1] = rect[i].x2;b[i * 2] = rect[i].y1;b[i * 2 + 1] = rect[i].y2;}// 对x坐标进行离散化sort(a, a + 2 * n);int lena = unique(a, a + 2 * n) - a; // 去重后的x坐标数量// 对y坐标进行离散化sort(b, b + 2 * n);int lenb = unique(b, b + 2 * n) - b; // 去重后的y坐标数量// 将矩形坐标映射到离散化后的索引for (int i = 0; i < n; i++) {rect[i].x1 = lower_bound(a, a + lena, rect[i].x1) - a;rect[i].x2 = lower_bound(a, a + lena, rect[i].x2) - a;rect[i].y1 = lower_bound(b, b + lenb, rect[i].y1) - b;rect[i].y2 = lower_bound(b, b + lenb, rect[i].y2) - b;// 标记被当前矩形覆盖的小格子for (int j = rect[i].x1; j < rect[i].x2; j++) {for (int k = rect[i].y1; k < rect[i].y2; k++) {c[j][k] = 1;}}}// 计算总面积for (int i = 0; i < lena - 1; i++) {for (int j = 0; j < lenb - 1; j++) {if (c[i][j]) {// 累加每个被覆盖小格子的实际面积ans += (a[i + 1] - a[i]) * (b[j + 1] - b[j]);}}}// 输出结果cout << ans;return 0;
}
【运行结果】
2
0 5 4 1
2 4 6 2
20