usaco-5.3.2 窗体面积

形式化题目

维护一个二维平面上的矩形窗体序列，每个窗体具有唯一标识符及两对角顶点坐标。支持以下动态操作：

创建窗体：加入新矩形，并将其置于图层最顶端；
置顶窗体：将指定矩形移动到图层最顶端；
置底窗体：将指定矩形移动到图层最底端；
删除窗体：从图层中移除指定矩形；
查询可见度：给定窗体标识符，求该矩形未被其上方任何矩形遮挡的可见区域面积占该矩形初始总面积的百分比，四舍五入保留 3 位小数。

正解

思路

本题窗体的最大特点在于具有严格的前后覆盖层级（Z-Order）。当查询某一窗体的可见面积时，只有在图层层级上位于其上方的窗体才会造成遮挡，位于其下方的窗体对其没有任何影响。

1. 图层层级维护

我们可以用一个列表维护当前所有存在的窗体，列表由底至顶排列：

创建新窗体：追加到列表末尾（即置顶）；
置顶操作：在列表中定位后取出，再追加到末尾；
置底操作：在列表中定位后取出，插入到列表头部；
删除操作：直接在列表中删除对应元素。

由于窗体标识符取自大小写字母及数字，同时存在的窗体数量最多不超过 $62$ 个，列表调整的代价极小。

2. 矩形切割（Rectangular Clipping）

针对单次查询，假设目标窗体为矩形 $R$ ，其上方有遮挡矩形序列 $C_1, C_2, \dots, C_k$ 。我们使用矩形切割法逐步精细化可见区域：维护一个初始仅包含目标矩形自身的未遮挡矩形集合 $S = \{ R \}$ 。依次考虑上方的每个遮挡矩形 $C_i$ ：对于 $S$ 中的每一个子矩形 $P = [x_1, x_2] \times [y_1, y_2]$ ：

若 $P$ 与 $C_i$ 无交集，则 $P$ 依然完全保留；
若 $P$ 与 $C_i$ 相交，则设它们的交集为 $[ix_1, ix_2] \times [iy_1, iy_2]$ ，交集部分被遮挡剔除。剩余的可见部分可以精确分割为至多 $4$ 个互不重叠的小矩形：
- 上方条带： $[x_1, x_2] \times [iy_2, y_2]$ （若 $y_2 > iy_2$ ）；
- 下方条带： $[x_1, x_2] \times [y_1, iy_1]$ （若 $y_1 < iy_1$ ）；
- 中间左侧条带： $[x_1, ix_1] \times [iy_1, iy_2]$ （若 $x_1 < ix_1$ ）；
- 中间右侧条带： $[ix_2, x_2] \times [iy_1, iy_2]$ （若 $x_2 > ix_2$ ）。

用切割后产生的新碎片替换原矩形 $P$ 。若集合 $S$ 中途被完全削减为空，说明目标窗体已被完全遮挡，可提前退出。

最终，集合 $S$ 中所有碎片的面积之和即为目标窗体的可见面积，乘以 $100$ 并除以窗体总面积即得所求百分比。

可视化流程

下图展示了一个矩形在被上层矩形部分遮挡时，被四条交集边界切割为至多 $4$ 个互不相交的可见碎片的过程：

graph TD
    A["目标矩形 P"] --> B{"与上层矩形 C 是否相交?"}
    B -- 否 --> C["保留完整矩形 P"]
    B -- 是 --> D["计算交集 [ix1, ix2] x [iy1, iy2]"]
    D --> E["切分出上方条带 (若有)"]
    D --> F["切分出下方条带 (若有)"]
    D --> G["切分出中间左侧条带 (若有)"]
    D --> H["切分出中间右侧条带 (若有)"]

代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88#!/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-04-18 10:00
# update_at: 2026-04-18 10:00

import sys

Rect = tuple[int, int, int, int]


def clip(rect: Rect, cover: Rect) -> list[Rect]:
    """计算矩形 rect 被矩形 cover 覆盖后留下的互不相交的子矩形列表。"""
    rx1, ry1, rx2, ry2 = rect
    cx1, cy1, cx2, cy2 = cover

    # 若无交集，rect 完整保留
    if rx2 <= cx1 or rx1 >= cx2 or ry2 <= cy1 or ry1 >= cy2:
        return [rect]

    # 求交集边界
    ix1, iy1 = max(rx1, cx1), max(ry1, cy1)
    ix2, iy2 = min(rx2, cx2), min(ry2, cy2)

    # 用交集四条边将 rect 割裂为至多 4 个不相交小矩形：上、下、左、右
    pieces: list[Rect] = []
    if ry2 > iy2:
        pieces.append((rx1, iy2, rx2, ry2))  # 上方条带
    if ry1 < iy1:
        pieces.append((rx1, ry1, rx2, iy1))  # 下方条带
    if rx1 < ix1:
        pieces.append((rx1, iy1, ix1, iy2))  # 中间左侧
    if rx2 > ix2:
        pieces.append((ix2, iy1, rx2, iy2))  # 中间右侧

    return pieces


def visible_area(target: Rect, covers: list[Rect]) -> int:
    """计算 target 矩形在依次被 covers 中的矩形遮挡后的剩余可见总面积。"""
    pieces = [target]
    for cov in covers:
        pieces = [sub for p in pieces for sub in clip(p, cov)]
        if not pieces:  # 已被完全遮挡
            break
    return sum((x2 - x1) * (y2 - y1) for x1, y1, x2, y2 in pieces)


def solve() -> None:
    lines = sys.stdin.read().split()
    windows: list[tuple[str, Rect]] = []  # 窗体栈：从底到顶排序
    out: list[str] = []

    for line in lines:
        op = line[0]
        args = line[2:-1].split(',')
        wid = args[0]

        if op == 'w':
            x1, y1, x2, y2 = map(int, args[1:])
            rect = (min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2))
            windows.append((wid, rect))  # 新建窗体自动置顶
        elif op == 't':
            idx = next(i for i, (w, _) in enumerate(windows) if w == wid)
            item = windows.pop(idx)
            windows.append(item)  # 置顶
        elif op == 'b':
            idx = next(i for i, (w, _) in enumerate(windows) if w == wid)
            item = windows.pop(idx)
            windows.insert(0, item)  # 置底
        elif op == 'd':
            idx = next(i for i, (w, _) in enumerate(windows) if w == wid)
            windows.pop(idx)
        elif op == 's':
            idx = next(i for i, (w, _) in enumerate(windows) if w == wid)
            target = windows[idx][1]
            covers = [w[1] for w in windows[idx + 1:]]  # 在其之上的所有窗体
            total = (target[2] - target[0]) * (target[3] - target[1])
            vis = visible_area(target, covers)
            ratio = vis * 100.0 / total
            out.append(f"{ratio:.3f}")

    print('\n'.join(out))


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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157/**
 * 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 12:08
 * update_at: 2026-10-06 12:08
 */

// main.cpp：窗体面积。
// 用一个窗体栈（从底到顶）维护层级顺序；
// 查询 s(I) 时，用矩形切割法把目标窗体依次被上方窗体遮挡后的可见碎片保留下来。

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

typedef long long ll;

const int MAXN = 70; // 同时存在的窗体最多 62 个（字母 + 数字），留点余量

// 一个窗体：标识符 + 对角坐标（保证 x1<x2, y1<y2）
struct Window {
    char id;
    ll x1, y1, x2, y2;
};

// 可见碎片矩形
struct Rect {
    ll x1, y1, x2, y2;
};

Window wins[MAXN]; // 窗体栈，wins[0] 最底，wins[top-1] 最顶
int top = 0;       // 栈中窗体个数

// 计算矩形面积
ll rect_area(const Rect &r) {
    return (r.x2 - r.x1) * (r.y2 - r.y1);
}

// 矩形切割：用遮挡矩形 cover 切割 rect，留下的碎片放入 out，返回碎片个数
// rect 与 cover 有交集时，交集被剔除，剩余部分分成至多 4 个互不相交的条带
int clip(const Rect &rect, const Rect &cover, Rect *out) {
    // 无交集：原矩形完整保留
    if (rect.x2 <= cover.x1 || rect.x1 >= cover.x2 ||
        rect.y2 <= cover.y1 || rect.y1 >= cover.y2) {
        out[0] = rect;
        return 1;
    }

    // 交集边界
    ll ix1 = std::max(rect.x1, cover.x1);
    ll iy1 = std::max(rect.y1, cover.y1);
    ll ix2 = std::min(rect.x2, cover.x2);
    ll iy2 = std::min(rect.y2, cover.y2);

    int cnt = 0;
    if (rect.y2 > iy2) { // 上方条带
        out[cnt].x1 = rect.x1; out[cnt].y1 = iy2;
        out[cnt].x2 = rect.x2; out[cnt].y2 = rect.y2;
        cnt++;
    }
    if (rect.y1 < iy1) { // 下方条带
        out[cnt].x1 = rect.x1; out[cnt].y1 = rect.y1;
        out[cnt].x2 = rect.x2; out[cnt].y2 = iy1;
        cnt++;
    }
    if (rect.x1 < ix1) { // 中间左侧条带
        out[cnt].x1 = rect.x1; out[cnt].y1 = iy1;
        out[cnt].x2 = ix1;     out[cnt].y2 = iy2;
        cnt++;
    }
    if (rect.x2 > ix2) { // 中间右侧条带
        out[cnt].x1 = ix2;     out[cnt].y1 = iy1;
        out[cnt].x2 = rect.x2; out[cnt].y2 = iy2;
        cnt++;
    }
    return cnt;
}

int main() {
    char line[256];
    std::vector<Rect> pieces; // 当前查询中还未被遮挡的可见碎片
    Rect tmp[8];              // clip 的临时碎片输出

    while (scanf("%255s", line) == 1) {
        std::string cmd = line;
        char op = cmd[0];
        // 逗号换成空格，方便 sscanf 按统一格式解析参数
        for (int i = 0; line[i] != '\0'; i++)
            if (line[i] == ',') line[i] = ' ';

        if (op == 'w') {
            // w(I,x,y,X,Y)：新建窗体，自动置顶
            char id;
            ll x1, y1, x2, y2;
            sscanf(line, " w ( %c %lld %lld %lld %lld )",
                   &id, &x1, &y1, &x2, &y2);
            if (x1 > x2) std::swap(x1, x2); // 对角点不保证左下在前后
            if (y1 > y2) std::swap(y1, y2);
            wins[top].id = id;
            wins[top].x1 = x1; wins[top].y1 = y1;
            wins[top].x2 = x2; wins[top].y2 = y2;
            top++;
        } else {
            // t/b/d/s 都是 t(I) 形式：先找到窗体在栈中的位置
            char id;
            sscanf(line, " %*c ( %c )", &id);
            int pos = -1;
            for (int i = 0; i < top; i++)
                if (wins[i].id == id) { pos = i; break; }

            if (op == 't') {
                // 置顶：取出后放到栈顶
                Window w = wins[pos];
                for (int i = pos; i < top - 1; i++) wins[i] = wins[i + 1];
                wins[top - 1] = w;
            } else if (op == 'b') {
                // 置底：取出后放到栈底
                Window w = wins[pos];
                for (int i = pos; i > 0; i--) wins[i] = wins[i - 1];
                wins[0] = w;
            } else if (op == 'd') {
                // 删除：从栈中移除
                for (int i = pos; i < top - 1; i++) wins[i] = wins[i + 1];
                top--;
            } else if (op == 's') {
                // 查询可见百分比：从栈顶往下直到目标窗体，依次切割
                pieces.clear();
                Rect all;
                all.x1 = wins[pos].x1; all.y1 = wins[pos].y1;
                all.x2 = wins[pos].x2; all.y2 = wins[pos].y2;
                pieces.push_back(all);

                for (int i = top - 1; i > pos && !pieces.empty(); i--) {
                    Rect cover;
                    cover.x1 = wins[i].x1; cover.y1 = wins[i].y1;
                    cover.x2 = wins[i].x2; cover.y2 = wins[i].y2;
                    std::vector<Rect> next_pieces;
                    for (int j = 0; j < (int)pieces.size(); j++) {
                        int cnt = clip(pieces[j], cover, tmp);
                        for (int k = 0; k < cnt; k++) next_pieces.push_back(tmp[k]);
                    }
                    pieces = next_pieces;
                }

                ll total = rect_area(all); // 窗体初始总面积，直接由坐标算出
                ll vis = 0; // 可见面积
                for (int j = 0; j < (int)pieces.size(); j++)
                    vis += rect_area(pieces[j]);
                // 乘 100 转百分比，四舍五入到 3 位小数
                printf("%.3f\n", (double)vis * 100.0 / (double)total);
            }
        }
    }
    return 0;
}

复杂度

时间复杂度：
- 窗体增删置顶置底操作：由于总窗体数 $N \leqslant 62$ ，单次列表操作时间复杂度为 $O(N)$ ；
- 查询操作：对于至多 $N$ 个遮挡矩形，每次切割将碎片分裂为互不相交的子矩形。在数据范围内，碎片总数规模极小，整体单次查询耗时在数毫秒以内；
- 总时间复杂度为 $O(Q \cdot N \cdot M)$ （其中 $Q$ 为操作总数， $M$ 为单次查询的最大碎片数），完全可以在时限内通过所有测试点。
空间复杂度： $O(N + M)$ ，仅需存储当前活跃的窗体列表及查询过程中的临时碎片集合。

总结

本题的关键在于利用矩形的正交性，通过“矩形切割”把遮挡问题转化为若干小矩形在被交集剔除后的无重叠分割。相比全局离散化扫描线，矩形切割法代码简短优雅，非常契合本题窗体数量小、图层顺序动态变化的特点。