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

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

前置条件

  • 基本 C++ 语法（第 2.1~2.2 章）
  • if/else 条件语句

🎯 学习目标

学完本章后，你将能够：

  1. 识别需要分类讨论的题目，系统枚举所有情形
  2. 处理坐标轴上的矩形交叉、覆盖、面积问题
  3. 判断两个矩形是否相交，计算交集面积
  4. 用差分思想处理网格上的矩形覆盖计数

2.5.1 分类讨论（Casework）

什么是分类讨论？

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

核心原则：

  1. 完备性：不遗漏任何情形
  2. 互斥性：情形之间没有重叠（或显式处理重叠）
  3. 验证：对每种情形验证边界值

示例：一维区间分类

问题： 给定两个区间 [a, b] 和 [c, d]，判断它们的关系（不相交、相接、相交、包含）。

情形1：b < c 或 d < a  →  完全不相交
      [a...b]  [c...d]   或   [c...d]  [a...b]

情形2：b == c 或 a == d  →  仅一个端点相接
      [a...b=c...d]

情形3：a <= c 且 b >= d  →  [c,d] 在 [a,b] 内部
情形4：c <= a 且 d >= b  →  [a,b] 在 [c,d] 内部

情形5：其他  →  部分重叠

#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 (b < c || d < a) {
        cout << "不相交\n";
    } else if (a <= c && b >= d) {
        cout << "[c,d] 在 [a,b] 内部（或相等）\n";
    } else if (c <= a && d >= b) {
        cout << "[a,b] 在 [c,d] 内部（或相等）\n";
    } else {
        cout << "部分重叠\n";
    }
    return 0;
}

分类讨论的技巧

技巧 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));
// 若结果 <= 0，说明不相交

技巧 3：画图 + 列举边界

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

USACO Bronze 典型：方向判断

问题（USACO 风格）： 奶牛从 (x, y) 出发，面朝 North/South/East/West。
给出「左转/右转/前进 D 步」指令，输出最终位置。

#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

两矩形是否相交

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

// 矩形 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;
}

交集面积

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)

交集左下：max(1,2)=2, max(1,2)=2
交集右上：min(4,6)=4, min(4,5)=4
交集面积：(4-2) × (4-2) = 4

两矩形的并集面积

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;  // 容斥原理
}

矩形内点的判断

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;
}

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

当有大量矩形叠加时，可以用二维差分数组统计每个格子被覆盖的次数。

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

const int MAXN = 1005;
int diff[MAXN][MAXN];  // 差分数组

// 矩形左下 (x1,y1)，右上 (x2,y2)，覆盖 +1
void add_rect(int x1, int y1, int x2, int y2) {
    diff[y1][x1]++;
    diff[y2][x1]--;
    diff[y1][x2]--;
    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 i = 1; i < MAXN; i++)
        for (int j = 1; j < MAXN; j++)
            diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
    
    // 统计覆盖面积
    long long covered = 0;
    for (int i = 1; i < MAXN; i++)
        for (int j = 1; j < MAXN; j++)
            if (diff[i][j] > 0) covered++;
    
    cout << covered << "\n";
    return 0;
}

⚠️ 常见错误

错误原因修复方案
边界情形遗漏只考虑「一般情况」，忽略端点相等逐一列出所有情形，验证 <= vs <
整数溢出坐标值大时 x * y 超过 int用 long long
矩形方向假设错误没有保证 x1<x2 y1<y2读入后 if(x1>x2) swap(x1,x2)
差分数组越界添加矩形时坐标超出范围检查坐标是否在数组范围内

💪 练习题

🟢 题目 1：矩形相交判断

给定两个矩形，判断它们是否有公共区域（交集面积 > 0），输出交集的坐标和面积，若不相交输出 0。

✅ 完整解答 
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long ax1,ay1,ax2,ay2,bx1,by1,bx2,by2;
    cin >> ax1 >> ay1 >> ax2 >> ay2;
    cin >> bx1 >> by1 >> bx2 >> by2;
    
    long long ix1=max(ax1,bx1), iy1=max(ay1,by1);
    long long ix2=min(ax2,bx2), iy2=min(ay2,by2);
    
    if (ix2 <= ix1 || iy2 <= iy1) cout << 0;
    else cout << (ix2-ix1)*(iy2-iy1);
    cout << "\n";
}

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

有 N 块矩形牧场（坐标均为 0~1000 的整数），求被至少一块牧场覆盖的总格数（每格 1×1）。

✅ 完整解答

思路： 用差分数组标记每个 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-1, y1~y2-1)
        diff[y1][x1]++;   diff[y2][x1]--;
        diff[y1][x2]--;   diff[y2][x2]++;
    }
    
    long long ans = 0;
    for (int i = 0; i <= 1000; i++)
        for (int j = 0; j <= 1000; j++) {
            if (i > 0) diff[i][j] += diff[i-1][j];
            if (j > 0) diff[i][j] += diff[i][j-1];
            if (i > 0 && j > 0) diff[i][j] -= diff[i-1][j-1];
            if (diff[i][j] > 0) ans++;
        }
    cout << ans << "\n";
}

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

给定一个矩形和 N 个点，将每个点分类：在矩形内部、在矩形边界上、在矩形外部。

✅ 完整解答 
#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_edge = (px==x1||px==x2) && (y1<=py&&py<=y2)
                    || (py==y1||py==y2) && (x1<=px&&px<=x2);
        bool inside = x1<px && px<x2 && y1<py && py<y2;
        if (on_edge) cout << "边界\n";
        else if (inside) cout << "内部\n";
        else cout << "外部\n";
    }
}

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