画图 - 题目列表

形式化题目

给定若干个左下角为 $(x_1,y_1)$ 、右上角为 $(x_2,y_2)$ 的矩形，统计所有至少被涂色一次的单位面积。重叠区域只计算一次。

思路

先看逐单位格判断的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:53
 */
// brute.cpp：小数据暴力解，逐个单位格检查是否被任意矩形覆盖。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int x1[105], y1[105], x2[105], y2[105];
    for (int i = 0; i < n; i++) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    }

    int answer = 0;
    for (int x = 0; x < 100; x++) {
        for (int y = 0; y < 100; y++) {
            bool covered = false;
            for (int i = 0; i < n; i++) {
                if (x1[i] <= x && x < x2[i] && y1[i] <= y && y < y2[i]) {
                    covered = true;
                    break;
                }
            }
            answer += covered;
        }
    }

    cout << answer << '\n';
    return 0;
}

坐标最大只有 $100$ ，可以把每个单位正方形 (x,y) 看成一个网格位置。读入矩形时，将半开区间 x1 <= x < x2、y1 <= y < y2 中的网格标记为 true。重复涂色不会改变布尔值，最后统计所有真值。

样例网格

样例中第一块矩形覆盖 $9$ 个格子，第二块覆盖 $8$ 个格子，重叠 $2$ 个格子，因此并集面积为 $9+8-2=15$ ：

y\x	1	2	3	4	5
4	#	#	#	#	#
3	#	#	#	#	#
2	#	#	#	.	.
1	#	#	#	.	.

# 表示至少被一个矩形覆盖的格子。第一块矩形 $(1,1)-(4,4)$ 覆盖 $3\times3=9$ 格，第二块 $(2,3)-(6,5)$ 覆盖 $4\times2=8$ 格，交集 $[2,4)\times[3,5)$ 共 2 格被算两次但只计一次。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:53
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    bool painted[101][101] = {};
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int x = x1; x < x2; x++) {
            for (int y = y1; y < y2; y++) {
                painted[x][y] = true;
            }
        }
    }

    int answer = 0;
    for (int x = 0; x <= 100; x++) {
        for (int y = 0; y <= 100; y++) {
            answer += painted[x][y];
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

每个矩形最多标记 $100\times100$ 个格子，时间复杂度为 $O(nC^2+C^2)$ ，其中 $C=100$ ；空间复杂度为 $O(C^2)$ 。

总结

坐标范围很小时，二维布尔数组是处理矩形覆盖并集的直接模型。关键是把连续区域拆成单位格，并使用半开区间 [x1,x2) × [y1,y2)，这样每个格子的面积恰好为 1。

画图

目录

形式化题目

思路

样例网格

代码

复杂度

总结