Rectangle Geometry
矩形几何
基本说明
本文涉及的题目均围绕边与坐标轴平行的矩形展开。
适用编程语言：所有语言
预备知识：青铜级（Bronze）- 时间复杂度（Time Complexity）
参考资料 |
|---|
USACO 7.1 - 矩形几何（Rectangle Geometry），本模块基于此内容编写 |
此类题目大多只涉及两个或三个正方形/矩形，遇到这类题目时，只需在纸上画出所有可能的情况，就能推理出解决方案。
示例：栅栏涂色（Fence Painting）
难度：青铜级（Bronze）- 简单（Easy）
http://oj.oldmoon.cn/p/U1516DB1
暴力解法（Slow Solution）
由于所有区间都在 [0, 100] 范围内，我们可以通过循环，将每个区间内所有长度为 1 的子区间标记为“已涂色”。最终，被标记的子区间总数就是答案。
时间复杂度：$\mathcal{O}(\text{最大坐标值})$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int MAX_POS = 100;
int main() {
freopen("paint.in", "r", stdin);
freopen("paint.out", "w", stdout);
int a, b, c, d;
cin >> a >> b >> c >> d;
vector<bool> painted(MAX_POS + 1);
// Add Farmer John's painted interval
for (int i = a; i < b; i++) { painted[i] = true; }
// Add Bessie's painted interval
for (int i = c; i < d; i++) { painted[i] = true; }
// Count the total amount of intervals painted
int total = 0;
for (bool i : painted) { total += i; }
cout << total << endl;
}然而，当约束条件更高时（例如坐标值最大达到 $10^9$），该解法将无法适用。
快速解法（Fast Solution）
先计算两个区间的长度之和，再减去它们的重叠部分长度，即可得到答案。
计算公式：$\text{总长度} = (b-a)+(d-c)-\text{区间}[a,b]与[c,d]的重叠长度$
官方解析将“计算重叠长度”拆分为多种情况，但我们可以用更简洁的方法实现：
若子区间 $[x,x+1]$ 同时包含在 $[a,b]$ 和 $[c,d]$ 中，则需满足 $a\le x$、$c\le x$、$x
因此，重叠长度的计算公式为：若 $\min(b,d)-\max(a,c)$ 为正数，则取该值；否则重叠长度为 0。
时间复杂度：$\mathcal{O}(1)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("paint.in", "r", stdin);
freopen("paint.out", "w", stdout);
int a, b, c, d;
cin >> a >> b >> c >> d;
int total = (b - a) + (d - c); // the sum of the two intervals
int intersection = max(min(b, d) - max(a, c), 0); // subtract the intersection
int ans = total - intersection;
cout << ans << "\n";
}示例：被遮挡的广告牌（Blocked Billboard）
该问题可看作上一个示例的“二维版本”。
难度：青铜级（Bronze）- 中等（Normal）
http://oj.oldmoon.cn/p/U1718DB1
暴力解法（Slow Solution）
时间复杂度：$\mathcal{O}((\text{最大坐标值})^2)$
由于所有坐标值都在 [-1000, 1000] 范围内，我们可以通过嵌套循环，遍历所有 $2000^2$ 个可能的“可见小正方形”，并判断每个小正方形是否可见。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int MAX_POS = 2000;
bool visible[MAX_POS][MAX_POS];
int main() {
freopen("billboard.in", "r", stdin);
freopen("billboard.out", "w", stdout);
for (int i = 0; i < 3; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// make all the coordinates positive
x1 += MAX_POS / 2;
y1 += MAX_POS / 2;
x2 += MAX_POS / 2;
y2 += MAX_POS / 2;
for (int x = x1; x < x2; x++) {
// Mark billboard area as visible, truck as not visible
for (int y = y1; y < y2; y++) { visible[x][y] = i < 2; }
}
}
// Count all visible billboard squares
int ans = 0;
for (int x = 0; x < MAX_POS; x++) {
for (int y = 0; y < MAX_POS; y++) { ans += visible[x][y]; }
}
cout << ans << endl;
}然而，当坐标值最大达到 $10^9$ 时，该解法将无法适用。
快速解法（Fast Solution）
时间复杂度：$\mathcal{O}(1)$
官方解析（Official Analysis）
C++ 代码
注意：创建一个 Rect 结构体来表示矩形，可使代码更易理解。
#include <bits/stdc++.h>
using namespace std;
struct Rect {
int x1, y1, x2, y2;
void read() { cin >> x1 >> y1 >> x2 >> y2; }
int area() { return (y2 - y1) * (x2 - x1); } // Area of the rectangle
};
int intersect(Rect p, Rect q) {
// Calculate overlap in x and y directions
int xOverlap = max(0, min(p.x2, q.x2) - max(p.x1, q.x1));
int yOverlap = max(0, min(p.y2, q.y2) - max(p.y1, q.y1));
return xOverlap * yOverlap; // Area of intersection
}
int main() {
freopen("billboard.in", "r", stdin);
freopen("billboard.out", "w", stdout);
Rect a, b, t; // billboards a, b, and the truck
a.read();
b.read();
t.read();
// Total visible area = area of both billboards minus area covered by truck
cout << a.area() + b.area() - intersect(a, t) - intersect(b, t) << endl;
}常用公式（Common Formulas）
警告！
若你已理解“被遮挡的广告牌（Blocked Billboard）”的快速解法，则可跳过本节内容。
矩形几何问题中，某些任务会频繁出现。例如，许多题目需要根据矩形的坐标计算两个或多个矩形的重叠面积，或判断两个矩形是否相交。本节将介绍这些常用公式。
注意：这些公式仅适用于“边与坐标轴平行”的矩形。
坐标表示（Coordinates）
一个矩形可由两个点表示：右上角顶点（top right，简称 tr）和左下角顶点（bottom left，简称 bl）。
在本模块中，我们约定：x 轴正方向为“向右”，y 轴正方向为“向上”。
计算面积（Finding area）
单个矩形的面积公式为：$\text{面积} = \text{宽} \times \text{长}$（$w \cdot l$）。
$\text{长}$（length）：矩形垂直边的长度。
$\text{宽}$（width）：矩形水平边的长度。
具体计算公式：
$\text{宽} = \text{tr}_x - \text{bl}_x$（右上角 x 坐标 - 左下角 x 坐标）
$\text{长} = \text{tr}_y - \text{bl}_y$（右上角 y 坐标 - 左下角 y 坐标）
$\text{面积} = \text{宽} \times \text{长}$
代码实现（Implementation）
C++ 代码
long long area(int bl_x, int bl_y, int tr_x, int tr_y) {
long long length = tr_y - bl_y;
long long width = tr_x - bl_x;
return length * width;
}判断两个矩形是否相交（Checking if two rectangles intersect）
给定两个矩形 a 和 b，只有两种情况它们不相交：
1. 矩形 a 的右上角 y 坐标 ≤ 矩形 b 的左下角 y 坐标（$\texttt{tr}_{a_y} \leq \texttt{bl}_{b_y}$），或矩形 a 的左下角 y 坐标 ≥ 矩形 b 的右上角 y 坐标（$\texttt{bl}_{a_y} \geq \texttt{tr}_{b_y}$）；
2. 矩形 a 的左下角 x 坐标 ≥ 矩形 b 的右上角 x 坐标（$\texttt{bl}_{a_x} \geq \texttt{tr}_{b_x}$），或矩形 a 的右上角 x 坐标 ≤ 矩形 b 的左下角 x 坐标（$\texttt{tr}_{a_x} \leq \texttt{bl}_{b_x}$）。
除上述两种情况外，两个矩形均相交。
代码实现（Implementation）
C++ 代码
bool intersect(vector<int> s1, vector<int> s2) {
int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
// 不相交的情况
if (bl_a_x >= tr_b_x || tr_a_x <= bl_b_x || bl_a_y >= tr_b_y || tr_a_y <= bl_b_y) {
return false;
} else {
return true;
}
}计算相交面积（Finding area of intersection）
我们默认两个矩形的相交部分仍是一个矩形。
首先计算相交矩形的“长”和“宽”：
宽（width）= $\min(\texttt{tr}_{a_x}, \texttt{tr}_{b_x}) - \max(\texttt{bl}_{a_x}, \texttt{bl}_{b_x})$（两个矩形右上角 x 坐标的最小值 - 两个矩形左下角 x 坐标的最大值）；
长（length）= $\min(\texttt{tr}_{a_y}, \texttt{tr}_{b_y}) - \max(\texttt{bl}_{a_y}, \texttt{bl}_{b_y})$（两个矩形右上角 y 坐标的最小值 - 两个矩形左下角 y 坐标的最大值）。
若“长”或“宽”为负数，则两个矩形不相交；若为 0，则两个矩形仅交于一点。将“长”与“宽”相乘，即可得到相交面积。
代码实现（Implementation）
C++ 代码
int inter_area(vector<int> s1, vector<int> s2) {
int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
return ((min(tr_a_x, tr_b_x) - max(bl_a_x, bl_b_x)) *
(min(tr_a_y, tr_b_y) - max(bl_a_y, bl_b_y)));
}练习题（Problems）
状态（Status） | 来源（Source） | 题目名称（Problem Name） | 难度（Difficulty） | 标签（Tags） |
|---|---|---|---|---|
青铜级（Bronze） | 正方形牧场（Square Pasture） | 简单（Easy） | 显示标签（Show Tags）：矩形（Rectangle） | |
青铜级（Bronze） | 被遮挡的广告牌 II（Blocked Billboard II） | 困难（Hard） | 显示标签（Show Tags）：矩形（Rectangle） | |
- | Codeforces（CF） | D3C - 白纸（White Sheet） | 困难（Hard） | 显示标签（Show Tags）：矩形（Rectangle） |
- | Codeforces（CF） | B. 两张桌子（Two Tables） | 困难（Hard） | 显示标签（Show Tags）：矩形（Rectangle） |