形成的区域

题目描述

在 $A\times B$ 的白纸（颜色 1）上依次叠放 $N$ 个颜色不同的不透明长方形，后放的盖住先放的，长方形边与纸边平行且都在纸内。求俯视时每种最终可见的颜色及其可见总面积（区域可以不连续），按颜色编号升序输出，面积为 0 的颜色不输出。

输入：第一行 $A\ B\ N$ （ $1\le A,B\le 10000$ ， $1\le N\le 1000$ ）；随后 $N$ 行每行 $llx\ lly\ urx\ ury\ color$ ，为该长方形的左下角、右上角坐标与颜色。

样例输入：20 20 3 / 2 2 18 18 2 / 0 8 19 19 3 / 8 0 10 19 4；样例输出：1 91 / 2 84 / 3 187 / 4 38。

思路

可见颜色的边界只能落在长方形的边上，于是把所有矩形的 x、y 端点坐标排序去重后做坐标压缩，平面被剖成至多 $(2N+1)^2$ 个整格同色的小格。对每个格从最上层往下找第一个覆盖它的长方形定色，再按格的真实宽高把面积累加到该颜色上。最后按颜色升序输出非零面积即可。

参考代码

Python 版：

python

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60#!/usr/bin/env python3
# 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-10-01 04:44
# update_at: 2026-10-01 04:44

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    A, B, n = next(data), next(data), next(data)

    # rects[0] 是白纸，之后按放置顺序叠放：后放者盖住先放者
    rects: list[tuple[int, int, int, int, int]] = [
        (0, 0, A, B, 1)  # 底层的白纸：颜色 1
    ]
    for _ in range(n):
        rects.append(
            tuple(next(data) for _ in range(5))  # llx, lly, urx, ury, color
        )
    rects.reverse()  # 倒序：从最顶层往下找，第一个盖住点的长方形即最终颜色

    # 坐标压缩：只保留出现过的 x/y（左下角与右上角都要收进来）
    xs = sorted({v for llx, _, urx, _, _ in rects for v in (llx, urx)})
    ys = sorted({v for _, lly, _, ury, _ in rects for v in (lly, ury)})
    nx, ny = len(xs) - 1, len(ys) - 1            # 格子数比坐标数少 1
    idx_x = {x: i for i, x in enumerate(xs)}     # 坐标 -> 压缩下标
    idx_y = {y: i for i, y in enumerate(ys)}

    # 长方形转成压缩下标后的格子区间 [x0, x1) x [y0, y1)：与原矩形覆盖完全相同的格子集合
    crects = [
        (idx_x[llx], idx_y[lly], idx_x[urx], idx_y[ury], color)
        for llx, lly, urx, ury, color in rects
    ]

    # ans[i][j] = 格子 (i, j)（x∈[xs[i],xs[i+1]], y∈[ys[j],ys[j+1]]）最终的颜色
    ans: list[list[int]] = [
        [
            next(  # 自顶向下第一个覆盖格子的长方形决定该格颜色
                color
                for x0, y0, x1, y1, color in crects
                if x0 <= i < x1 and y0 <= j < y1
            )
            for j in range(ny)
        ]
        for i in range(nx)
    ]

    area = [0] * 1001  # 颜色编号 1..1000，area[c] 为可见面积
    for i in range(nx):
        for j in range(ny):
            area[ans[i][j]] += (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j])

    print('\n'.join(f'{c} {area[c]}' for c in range(1, 1001) if area[c]))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * 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-10-06 10:11
 * update_at: 2026-10-06 10:11
 */
// main.cpp：坐标压缩后逐格定色，统计每种颜色的可见面积。
#include <algorithm>
#include <cstdio>

typedef long long ll;

const int MAXN = 1005;     // 长方形数量上限（含底层白纸）
const int MAXC = 10005;    // 坐标值域上界，坐标到压缩下标可直接用数组映射
const int MAXCOLOR = 1000; // 颜色编号 1..1000

ll A, B, n;

ll llx[MAXN], lly[MAXN], urx[MAXN], ury[MAXN], col[MAXN]; // 每个长方形的原坐标与颜色
ll xs[2 * MAXN], ys[2 * MAXN]; // 排序去重后的 x / y 断点坐标
ll xid[MAXC], yid[MAXC];       // 坐标 -> 压缩下标
ll area[MAXCOLOR + 1];         // area[c] = 颜色 c 的最终可见面积

int main() {
    scanf("%lld %lld %lld", &A, &B, &n);

    // 白纸作为最底层长方形，颜色为 1；下标越大表示叠得越高。
    llx[0] = 0; lly[0] = 0; urx[0] = A; ury[0] = B; col[0] = 1;
    for (ll i = 1; i <= n; i++) {
        scanf("%lld %lld %lld %lld %lld", &llx[i], &lly[i], &urx[i], &ury[i], &col[i]);
    }

    // 收集所有 x / y 端点（白纸贡献 0、A 与 0、B），排序去重得到断点。
    ll xn = 0, yn = 0;
    for (ll i = 0; i <= n; i++) {
        xs[xn++] = llx[i];
        xs[xn++] = urx[i];
        ys[yn++] = lly[i];
        ys[yn++] = ury[i];
    }
    std::sort(xs, xs + xn);
    xn = std::unique(xs, xs + xn) - xs;
    std::sort(ys, ys + yn);
    yn = std::unique(ys, ys + yn) - ys;

    // 坐标 -> 压缩下标，方便长方形区间与格子下标直接比较。
    for (ll i = 0; i < xn; i++) xid[xs[i]] = i;
    for (ll i = 0; i < yn; i++) yid[ys[i]] = i;

    // 格 (i, j) 覆盖 [xs[i], xs[i+1]) x [ys[j], ys[j+1])，内部无边界线所以整格同色；
    // 自顶层向下找第一个覆盖它的长方形即该格颜色，白纸兜底为颜色 1。
    for (ll i = 0; i + 1 < xn; i++) {
        for (ll j = 0; j + 1 < yn; j++) {
            ll c = 1;
            for (ll k = n; k >= 1; k--) {
                if (xid[llx[k]] <= i && i < xid[urx[k]] &&
                    yid[lly[k]] <= j && j < yid[ury[k]]) {
                    c = col[k];
                    break;
                }
            }
            area[c] += (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j]);
        }
    }

    for (ll c = 1; c <= MAXCOLOR; c++) {
        if (area[c] > 0) printf("%lld %lld\n", c, area[c]);
    }
    return 0;
}

目录

题目描述

思路

参考代码