📖 第 2.5 章：分类讨论与矩形几何

⏱ 预计阅读时间：55 分钟 | 难度：🟢 入门（USACO Bronze 核心技能）

前置条件

基本 C++ 语法（第 2.1~2.2 章）
if/else 条件语句
会读入整数、输出结果
知道平面直角坐标系中 x 表示横坐标、y 表示纵坐标

🎯 学习目标

学完本章后，你将能够：

识别需要分类讨论的题目，系统枚举所有情形
用「先画图、再列边界、最后写代码」的方法避免漏情况
处理坐标轴上的矩形交叉、覆盖、面积问题
判断两个矩形是否相交，计算交集面积
用差分思想处理网格上的矩形覆盖计数
读懂并实现 USACO Bronze 中常见的矩形覆盖题

本章学习路线

本章分成两条主线：

分类讨论：当题目存在多种情况时，如何不遗漏、不重复地处理。
矩形几何：当题目出现坐标、矩形、覆盖、相交时，如何把图形问题转成 min/max 和面积计算。

建议初学者按下面的顺序学习：

先画图理解题意
    ↓
找出关键边界：相等、刚好接触、完全覆盖、完全分离
    ↓
用 if/else 或 min/max 表达这些情况
    ↓
用样例和自己构造的边界数据检查代码

💡 本章的重点不是记住某个模板，而是学会把「看起来复杂的情况」拆成一组清晰、可验证的小情况。

2.5.1 分类讨论（Casework）

什么是分类讨论？

当问题的答案取决于若干个「互斥情形」时，需要逐一枚举每种情形，分别处理。

举几个简单例子：

一个数是正数、负数还是零？
两个区间是不相交、刚好相接，还是有重叠？
一个点在矩形内部、边界上，还是外部？
一个矩形是否被另一个矩形挡住了一部分？

这些问题都有一个共同点：不能只写一个公式就结束，而是要先判断当前输入属于哪一种情况。

核心原则：

完备性：不遗漏任何情形。
互斥性：不同情形之间最好不要重叠；如果会重叠，要明确优先级。
边界验证：特别检查 等于、刚好接触、刚好覆盖 这些边界值。

分类讨论的通用步骤

做分类讨论题时，可以按照下面四步来：

画图：把题目中的对象画出来，比如区间、矩形、运动方向。
找边界：思考什么时候答案会发生变化，例如两个区间端点相等时。
列情况：把所有可能情况列出来，尽量保证没有遗漏。
写条件：把每种情况翻译成 C++ 的 if / else if / else。

例如：

if (第一种情况) {
    // 处理第一种情况
} else if (第二种情况) {
    // 处理第二种情况
} else {
    // 剩余情况
}

这里最后的 else 很重要，它经常用于兜底：当前面所有明确列出的情况都不满足时，就进入最后一种情况。

示例：一维区间分类

题目描述：

给定两个闭区间 [a, b] 和 [c, d]，其中 a <= b，c <= d。请判断这两个区间的关系：

完全不相交：两个区间之间有空隙。
仅端点相接：两个区间只有一个端点相同，没有长度上的重叠。
一个包含另一个：其中一个区间完全覆盖另一个区间。
部分重叠：两个区间有公共部分，但谁也没有完全包含谁。

先不要急着写代码，可以先画图：

情况 1：完全不相交
[a-----b]   [c-----d]
或
[c-----d]   [a-----b]

情况 2：仅端点相接
[a-----b]
      [c-----d]     其中 b == c

情况 3：一个区间包含另一个区间
[a-----------b]
   [c-----d]

情况 4：部分重叠
[a--------b]
     [c--------d]

接下来把图翻译成条件。

关键边界：`<` 和 `==` 的区别

如果 b < c，说明 [a,b] 在 [c,d] 左边，并且中间有空隙。
如果 b == c，说明两个区间只在一个点相接。
如果 b > c，说明它们至少在横轴上有重叠或包含关系。

因此，在分类时，通常要先处理更特殊的情况，比如「完全不相交」和「端点相接」。

💡 CPP 代码（31 行）

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;  // 区间 [a,b] 和 [c,d]

    // 如果输入不保证左端点 <= 右端点，可以先修正
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);

    if (b < c || d < a) {
        cout << "完全不相交\n";
    } else if (b == c || d == a) {
        cout << "仅端点相接\n";
    } else if (a <= c && d <= b) {
        cout << "[c,d] 在 [a,b] 内部（或相等）\n";
    } else if (c <= a && b <= d) {
        cout << "[a,b] 在 [c,d] 内部（或相等）\n";
    } else {
        cout << "部分重叠\n";
    }
    return 0;
}

初学者常见疑问：为什么顺序很重要？

在 if / else if 中，程序会从上到下检查条件，遇到第一个满足的条件就执行，不会再继续检查后面的条件。

例如两个区间 [1, 5] 和 [1, 5]：

它既满足 [c,d] 在 [a,b] 内部。
也满足 [a,b] 在 [c,d] 内部。

这种情况并不是错误，而是说明两个区间相等。我们只要在题目要求的分类里确定一个输出即可。

💡 如果题目对「完全相等」有单独要求，就应该在包含判断之前先写 if (a == c && b == d)。

分类讨论的技巧

技巧 1：排序后减少情形数

对输入排序，可以将多种对称情形合并：

// 例：确保 a <= b（避免分别处理 a<b 和 a>b 两种情形）
if (a > b) swap(a, b);

技巧 2：用 min/max 简化区间操作

如果只关心两个区间的重叠长度，可以不必列出所有关系，而是直接算交集。

// 两区间 [a,b] 和 [c,d] 的交集长度
long long overlap = max(0LL, min(b, d) - max(a, c));

这个公式的含义是：

交集左端点是两个左端点中较大的那个：max(a, c)。
交集右端点是两个右端点中较小的那个：min(b, d)。
如果右端点小于等于左端点，说明没有正长度重叠。

注意：上面公式适合把区间看成 [a,b) 和 [c,d) 这种「左闭右开」长度模型。若是闭区间并且要统计整数点个数，公式会略有不同。

技巧 3：画图 + 列举边界

分类讨论题必须动手画图，列出所有边界情况逐一验证。至少要检查：

完全分离
刚好相接
部分重叠
一个完全包含另一个
两者完全相等

技巧 4：优先写「容易判断的反面」

有些题目直接判断「相交」比较麻烦，但判断「不相交」很简单。

例如两个区间不相交只有两种情况：

b <= c || d <= a

那么相交就是它的反面：

!(b <= c || d <= a)

矩形相交也会用到同样的思想。

USACO Bronze 典型：方向判断

题目描述（USACO 风格）：

一头奶牛站在二维平面上，初始位置是 (0, 0)，初始方向朝北。接下来会给出 N 条指令，每条指令可能是下面三种之一：

left：原地向左转 90 度。
right：原地向右转 90 度。
forward D：沿当前朝向前进 D 步。

请输出执行完所有指令后，奶牛的最终坐标。

这个题看起来像模拟题，但本质上也需要分类讨论：

当前方向是北、东、南、西中的哪一个？
当前指令是左转、右转，还是前进？
如果前进，不同方向对应的 x、y 变化不同。

朴素写法：直接分类讨论

最直观的写法是：

if (dir == "N") y += d;
else if (dir == "S") y -= d;
else if (dir == "E") x += d;
else if (dir == "W") x -= d;

这种写法容易理解，但如果转向逻辑也都用字符串分类，代码会比较长。

更简洁的写法：方向编号

我们可以把四个方向按顺时针编号：

0: North
1: East
2: South
3: West

这样右转就是编号 +1，左转就是编号 -1。为了避免出现负数，可以写成：

// 左转：dir - 1
// 加 4 是为了避免负数，再对 4 取模
(dir + 3) % 4

💡 CPP 代码（28 行）

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 方向编码：0=N, 1=E, 2=S, 3=W
    // dx/dy 对应四个方向的位移
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    
    int x = 0, y = 0, dir = 0;  // 初始位置和方向
    int n; cin >> n;
    
    while (n--) {
        string cmd; cin >> cmd;
        if (cmd == "left") {
            dir = (dir + 3) % 4;   // 左转 = (dir-1+4)%4
        } else if (cmd == "right") {
            dir = (dir + 1) % 4;   // 右转
        } else {
            int d; cin >> d;
            x += dx[dir] * d;
            y += dy[dir] * d;
        }
    }
    
    cout << x << " " << y << "\n";
    return 0;
}

2.5.2 矩形几何

坐标系中的矩形表示

竞赛中的矩形通常是轴对齐矩形，也就是矩形的边和坐标轴平行。它一般用两个对角顶点表示：

左下角：(x1, y1)
右上角：(x2, y2)

通常满足：

x1 < x2, y1 < y2

画出来是这样：

y
↑
y2 +----------+
   |          |
y1 +----------+→ x
   x1        x2

如果题目没有保证 x1 < x2、y1 < y2，读入后要先修正：

if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);

面积为什么是 `(x2 - x1) * (y2 - y1)`？

矩形的宽度是横坐标差：

width = x2 - x1

矩形的高度是纵坐标差：

height = y2 - y1

所以面积是：

area = (x2 - x1) * (y2 - y1)

例如矩形 (1, 2) 到 (4, 6)：

宽度：4 - 1 = 3
高度：6 - 2 = 4
面积：3 * 4 = 12

一个重要习惯：把矩形看成半开区间

在很多竞赛题里，矩形 (x1, y1, x2, y2) 表示：

x1 <= x < x2
y1 <= y < y2

也就是左边界和下边界算进去，右边界和上边界不算进去。这样做的好处是：

面积正好是 (x2 - x1) * (y2 - y1)。
两个矩形只在边界接触时，交集面积是 0。
用差分数组统计格子时更方便。

例如矩形 (0,0)-(2,2) 覆盖的是下面 4 个 1×1 小格子：

(0,1) (1,1)
(0,0) (1,0)

它的面积是 2 * 2 = 4。

两矩形是否相交

关键规则： 两矩形不相交，当且仅当一个矩形完全在另一个的左边、右边、下边或上边。

也就是说，如果出现下面任意一种情况，它们就没有正面积交集：

A 在 B 的左边：ax2 <= bx1
B 在 A 的左边：bx2 <= ax1
A 在 B 的下边：ay2 <= by1
B 在 A 的下边：by2 <= ay1

用图理解其中一种：

A 在 B 左边：

A             B
+---+         +---+
|   |         |   |
+---+         +---+
ax2 <= bx1

所以判断相交时，可以先判断「不相交」，再取反。

// 矩形 A: (ax1,ay1)-(ax2,ay2)
// 矩形 B: (bx1,by1)-(bx2,by2)
bool intersects(long long ax1, long long ay1, long long ax2, long long ay2,
                long long bx1, long long by1, long long bx2, long long by2) {
    // A 完全在 B 左边 or 右边 or 下边 or 上边
    if (ax2 <= bx1 || bx2 <= ax1 || ay2 <= by1 || by2 <= ay1)
        return false;
    return true;
}

💡 这里使用 <=，表示两个矩形如果只是边贴边，没有面积重叠，就不算相交。

交集面积

计算两个矩形的交集，可以把问题拆成两个一维问题：

x 方向的重叠长度
y 方向的重叠长度

交集矩形的左下角和右上角分别是：

交集左下角：max(两个左边界), max(两个下边界)
交集右上角：min(两个右边界), min(两个上边界)

对应到代码就是：

long long intersection_area(long long ax1, long long ay1, long long ax2, long long ay2,
                            long long bx1, long long by1, long long bx2, long long by2) {
    long long ix1 = max(ax1, bx1);
    long long iy1 = max(ay1, by1);
    long long ix2 = min(ax2, bx2);
    long long iy2 = min(ay2, by2);

    if (ix2 <= ix1 || iy2 <= iy1) return 0;  // 不相交，或只是边界相接
    return (ix2 - ix1) * (iy2 - iy1);
}

逐步追踪示例：

矩形 A: (1,1)-(4,4)
矩形 B: (2,2)-(6,5)

第 1 步：求交集左下角
x = max(1,2) = 2
y = max(1,2) = 2
所以左下角是 (2,2)

第 2 步：求交集右上角
x = min(4,6) = 4
y = min(4,5) = 4
所以右上角是 (4,4)

第 3 步：求面积
宽 = 4 - 2 = 2
高 = 4 - 2 = 2
面积 = 2 * 2 = 4

再看一个没有面积重叠的例子：

矩形 A: (0,0)-(2,2)
矩形 B: (2,0)-(4,2)

它们只是边界接触。
交集宽度 = min(2,4) - max(0,2) = 2 - 2 = 0
所以交集面积是 0。

两矩形的并集面积

两个矩形的并集面积，指的是至少被其中一个矩形覆盖的面积。

如果直接写：

并集面积 = A 的面积 + B 的面积

会出现一个问题：重叠部分被算了两次。

所以要把重叠部分减掉一次：

并集面积 = A 的面积 + B 的面积 - A 与 B 的交集面积

这就是最简单的容斥思想。

long long union_area(long long ax1, long long ay1, long long ax2, long long ay2,
                     long long bx1, long long by1, long long bx2, long long by2) {
    long long areaA = (ax2 - ax1) * (ay2 - ay1);
    long long areaB = (bx2 - bx1) * (by2 - by1);
    long long inter = intersection_area(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2);
    return areaA + areaB - inter;
}

举例：

矩形 A 面积 = 12
矩形 B 面积 = 10
重叠面积 = 4

如果直接相加：12 + 10 = 22，重叠部分多算了一次。
正确答案：12 + 10 - 4 = 18

💡 对两个矩形求并集面积时，这个公式很好用；但如果是三个或更多矩形，重叠关系会更复杂，通常要用扫描线、差分数组或更系统的容斥方法。

矩形内点的判断

判断一个点和矩形的关系时，要先看题目要求：

如果题目问点是否在矩形「内部或边界上」，使用 <=。
如果题目只问点是否在严格内部，使用 <。
如果题目要把边界单独分类，就要分别判断「边界」和「内部」。

bool point_in_rect(long long px, long long py,
                   long long x1, long long y1, long long x2, long long y2) {
    return x1 <= px && px <= x2 && y1 <= py && py <= y2;
}

例如矩形 (0,0)-(3,2)：

点 (1,1) 在内部。
点 (0,1) 在左边界上。
点 (3,2) 在右上角边界上。
点 (4,1) 在外部。

进阶：N 个矩形的覆盖面积（差分法）

当有大量矩形叠加时，如果逐个格子暴力标记，有时会比较慢；如果坐标范围不大，可以用二维差分数组统计每个格子被覆盖的次数。

先理解一维差分

假设有一个数组，我们想让区间 [l, r) 全部加 1，可以这样做：

diff[l]++;
diff[r]--;

最后从左到右做前缀和，就能知道每个位置被加了多少次。

二维差分是同样的思想，只是从「线段」变成「矩形」。

二维差分如何给矩形加 1？

如果要给矩形 [x1, x2) × [y1, y2) 覆盖区域加 1，做四个角的修改：

diff[y1][x1]++;
diff[y1][x2]--;
diff[y2][x1]--;
diff[y2][x2]++;

可以把它理解为：

从左下角开始加上影响。
到右边界之后取消影响。
到上边界之后取消影响。
右上角被取消了两次，所以要补回来一次。

💡 C++ 代码（45 行）

#include <bits/stdc++.h>
using namespace std;

const int MAX_COORD = 1000;                 // 坐标范围假设为 0~1000
int diff[MAX_COORD + 2][MAX_COORD + 2];     // 多开空间，方便处理 x2/y2

// 给矩形 [x1,x2) × [y1,y2) 覆盖区域 +1
void add_rect(int x1, int y1, int x2, int y2) {
    diff[y1][x1]++;
    diff[y1][x2]--;
    diff[y2][x1]--;
    diff[y2][x2]++;
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        add_rect(x1, y1, x2, y2);
    }

    // 二维前缀和还原每个格子的覆盖次数
    for (int y = 0; y <= MAX_COORD; y++) {
        for (int x = 0; x <= MAX_COORD; x++) {
            if (y > 0) diff[y][x] += diff[y - 1][x];
            if (x > 0) diff[y][x] += diff[y][x - 1];
            if (y > 0 && x > 0) diff[y][x] -= diff[y - 1][x - 1];
        }
    }

    // 统计被至少一个矩形覆盖的 1×1 格子
    // 左下角最大只能到 (999,999)，因为格子 [999,1000) 才是最后一格
    long long covered = 0;
    for (int y = 0; y < MAX_COORD; y++) {
        for (int x = 0; x < MAX_COORD; x++) {
            if (diff[y][x] > 0) covered++;
        }
    }

    cout << covered << "\n";
    return 0;
}

为什么统计的是格子，不是点？

坐标范围是 0~1000 时，格子通常是：

横坐标区间：[0,1), [1,2), ..., [999,1000)
纵坐标区间：[0,1), [1,2), ..., [999,1000)

所以共有 1000 × 1000 个 1×1 格子。数组下标 diff[y][x] 可以理解为左下角是 (x,y) 的那个小格子的覆盖次数。

⚠️ 常见错误

错误	原因	修复方案
边界情形遗漏	只考虑「一般情况」，忽略端点相等	逐一列出所有情形，验证 `<=` vs `<`
把相接误判为相交	两个矩形只是边贴边，交集面积其实是 `0`	判断不相交时使用 `<=`，不是 `<`
整数溢出	坐标值大时 `x * y` 超过 int	面积、答案统一用 `long long`
矩形方向假设错误	没有保证 `x1 < x2`、`y1 < y2`	读入后必要时用 `swap` 修正
差分数组越界	添加矩形时坐标超出范围，或没有给 `x2/y2` 多开空间	数组通常多开一格，例如 `1002 × 1002`
把点和格子混淆	坐标点数量和 `1×1` 格子数量不是一回事	覆盖面积题统计的是格子，不是坐标点
行列下标写反	`diff[y][x]` 和 `diff[x][y]` 混用	统一约定第一维是 `y`，第二维是 `x`，并全程保持一致

调试建议

写完矩形题后，可以自己构造下面几组数据检查：

完全不相交：答案应该是 0。
刚好边界相接：交集面积也应该是 0。
一个矩形完全包含另一个矩形：交集面积应该等于小矩形面积。
两个矩形完全相同：交集面积应该等于任意一个矩形的面积。
只有部分重叠：手算一次宽度、高度，再和程序输出对比。

本章小结

本章最重要的思想可以总结为三句话：

分类讨论先画图：不要凭感觉写条件，先把所有情况画出来。
矩形问题拆成两个方向：分别处理 x 方向和 y 方向，再把结果合起来。
覆盖问题优先想差分：当矩形很多、坐标范围不大时，二维差分比逐块暴力更清晰。

常用公式：

// 矩形面积
area = (x2 - x1) * (y2 - y1);

// 两矩形交集边界
ix1 = max(ax1, bx1);
iy1 = max(ay1, by1);
ix2 = min(ax2, bx2);
iy2 = min(ay2, by2);

// 两矩形交集面积
intersection = max(0LL, ix2 - ix1) * max(0LL, iy2 - iy1);

💪 练习题

🟢 题目 1：矩形相交判断

题目描述：

给定两个轴对齐矩形 A 和 B。每个矩形用四个整数表示：

x1 y1 x2 y2

其中 (x1, y1) 是矩形左下角，(x2, y2) 是矩形右上角，并且 x1 < x2、y1 < y2。

请判断两个矩形是否存在正面积交集：

如果存在，输出交集面积。
如果不存在，输出 0。

注意：如果两个矩形只是边界相接，例如一个矩形的右边界等于另一个矩形的左边界，那么交集面积为 0。

输入格式：

ax1 ay1 ax2 ay2
bx1 by1 bx2 by2

输出格式：

一个整数，表示两个矩形的交集面积

样例输入：

1 1 4 4
2 2 6 5

样例输出：

样例解释：

两个矩形的交集是 (2,2)-(4,4)，宽度为 2，高度为 2，面积为 4。

✅ 完整解答

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long ax1, ay1, ax2, ay2;
    long long bx1, by1, bx2, by2;
    cin >> ax1 >> ay1 >> ax2 >> ay2;
    cin >> bx1 >> by1 >> bx2 >> by2;

    long long ix1 = max(ax1, bx1);
    long long iy1 = max(ay1, by1);
    long long ix2 = min(ax2, bx2);
    long long iy2 = min(ay2, by2);

    if (ix2 <= ix1 || iy2 <= iy1) {
        cout << 0 << "\n";
    } else {
        cout << (ix2 - ix1) * (iy2 - iy1) << "\n";
    }

    return 0;
}

🟡 题目 2：奶牛放牧区域（USACO Bronze 风格）

题目描述：

农夫 John 有 N 块矩形牧场。每块牧场的边都与坐标轴平行，且坐标都是 0~1000 之间的整数。

每块牧场用左下角 (x1, y1) 和右上角 (x2, y2) 表示。它覆盖所有满足下面条件的 1×1 小格子：

x1 <= x < x2
y1 <= y < y2

如果多块牧场重叠，重叠部分只计算一次。请你求出被至少一块牧场覆盖的总格数，也就是覆盖总面积。

输入格式：

N
x1 y1 x2 y2
x1 y1 x2 y2
...

输出格式：

一个整数，表示被覆盖的 1×1 格子数量

样例输入：

样例输出：

样例解释：

第一块牧场面积是 4。
第二块牧场面积是 4。
它们重叠了 1 个格子。
第三块牧场面积是 1。
总覆盖面积是 4 + 4 - 1 + 1 = 8。

✅ 完整解答

思路： 用差分数组标记每个 1×1 格子被覆盖的次数，最后统计覆盖次数 >= 1 的格子数。

#include <bits/stdc++.h>
using namespace std;

int diff[1002][1002];

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // 给矩形 [x1,x2) × [y1,y2) 加 1
        diff[y1][x1]++;
        diff[y1][x2]--;
        diff[y2][x1]--;
        diff[y2][x2]++;
    }

    long long ans = 0;
    for (int y = 0; y <= 1000; y++) {
        for (int x = 0; x <= 1000; x++) {
            if (y > 0) diff[y][x] += diff[y - 1][x];
            if (x > 0) diff[y][x] += diff[y][x - 1];
            if (y > 0 && x > 0) diff[y][x] -= diff[y - 1][x - 1];

            // 只统计左下角为 (x,y) 的 1×1 格子，最大到 (999,999)
            if (x < 1000 && y < 1000 && diff[y][x] > 0) ans++;
        }
    }

    cout << ans << "\n";
    return 0;
}

🔴 题目 3：矩形分类问题（综合）

题目描述：

给定一个轴对齐矩形和 N 个点。请判断每个点与矩形的关系：

如果点在矩形四条边上，输出 边界。
如果点在矩形内部，但不在边界上，输出 内部。
如果点不在矩形内部，也不在边界上，输出 外部。

矩形由左下角 (x1, y1) 和右上角 (x2, y2) 给出，保证 x1 < x2、y1 < y2。

输入格式：

x1 y1 x2 y2
N
px py
px py
...

输出格式：

对每个点输出一行：边界、内部 或 外部。

样例输入：

样例输出：

内部
边界
边界
外部
边界

样例解释：

(1,1) 的横纵坐标都严格在矩形范围内，所以是内部。
(0,2) 在左边界上。
(4,3) 是右上角顶点，属于边界。
(5,1) 在矩形外部。
(2,3) 在上边界上。

✅ 完整解答

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int n;
    cin >> n;

    while (n--) {
        long long px, py;
        cin >> px >> py;

        bool on_vertical_edge = (px == x1 || px == x2) && (y1 <= py && py <= y2);
        bool on_horizontal_edge = (py == y1 || py == y2) && (x1 <= px && px <= x2);
        bool on_edge = on_vertical_edge || on_horizontal_edge;

        bool inside = x1 < px && px < x2 && y1 < py && py < y2;

        if (on_edge) cout << "边界\n";
        else if (inside) cout << "内部\n";
        else cout << "外部\n";
    }

    return 0;
}

🔴 题目 4：USACO Bronze — 遮挡广告牌

题目描述：

一面墙上贴了两块广告牌，随后一辆卡车停在墙前，挡住了其中一部分区域。广告牌和卡车在墙上的投影都可以看作轴对齐矩形。

现在给出：

第一块广告牌的矩形坐标。
第二块广告牌的矩形坐标。
卡车遮挡区域的矩形坐标。

请计算两块广告牌仍然可见的总面积。

注意：

两块广告牌之间不会相互遮挡。
卡车可能不遮挡某块广告牌。
卡车可能只遮挡广告牌的一部分。
卡车也可能完全遮挡某块广告牌。
如果卡车只和广告牌边界接触，不会减少可见面积。

输入格式：

三行，每行 4 个整数：

x1 y1 x2 y2
x1 y1 x2 y2
x1 y1 x2 y2

分别表示广告牌 1、广告牌 2、卡车遮挡区域。每个矩形都由左下角和右上角表示。

输出格式：

一个整数，表示两块广告牌仍然可见的总面积

样例输入：

1 2 3 5
6 0 10 4
2 1 8 3

样例输出：

样例解释：

广告牌 1 的面积是 (3 - 1) * (5 - 2) = 6。卡车与广告牌 1 的交集是 (2,2)-(3,3)，面积是 1，所以广告牌 1 可见面积是 5。

广告牌 2 的面积是 (10 - 6) * (4 - 0) = 16。卡车与广告牌 2 的交集是 (6,1)-(8,3)，面积是 4，所以广告牌 2 可见面积是 12。

总可见面积是 5 + 12 = 17。

✅ 完整解答

核心思路： 分类讨论 + 容斥。总面积 = 广告牌1面积 + 广告牌2面积 - 广告牌1被卡车遮挡面积 - 广告牌2被卡车遮挡面积。每块广告牌与卡车的遮挡面积用矩形交集公式计算。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 计算两个矩形的交集面积
ll inter_area(ll ax1, ll ay1, ll ax2, ll ay2,
              ll bx1, ll by1, ll bx2, ll by2) {
    ll ix1 = max(ax1, bx1), iy1 = max(ay1, by1);
    ll ix2 = min(ax2, bx2), iy2 = min(ay2, by2);
    if (ix2 <= ix1 || iy2 <= iy1) return 0;
    return (ix2 - ix1) * (iy2 - iy1);
}

int main() {
    ll a1x1, a1y1, a1x2, a1y2;  // 广告牌1
    ll a2x1, a2y1, a2x2, a2y2;  // 广告牌2
    ll tx1, ty1, tx2, ty2;       // 卡车
    cin >> a1x1 >> a1y1 >> a1x2 >> a1y2;
    cin >> a2x1 >> a2y1 >> a2x2 >> a2y2;
    cin >> tx1 >> ty1 >> tx2 >> ty2;

    ll area1 = (a1x2 - a1x1) * (a1y2 - a1y1);
    ll area2 = (a2x2 - a2x1) * (a2y2 - a2y1);
    ll covered1 = inter_area(a1x1, a1y1, a1x2, a1y2, tx1, ty1, tx2, ty2);
    ll covered2 = inter_area(a2x1, a2y1, a2x2, a2y2, tx1, ty1, tx2, ty2);

    cout << area1 + area2 - covered1 - covered2 << "\n";
    return 0;
}

复杂度分析： 时间 O(1)，空间 O(1)。只需计算几个矩形的面积和交集，常数时间完成。

💡 章节联系： 矩形几何是 USACO Bronze 的高频题型之一（约占 15%），常与前缀和（差分数组）结合。掌握后可直接用于解决「覆盖面积」「重叠判断」等问题。

C++ 竞赛编程：USACO 学习指南