REALHW156 爱丽丝的人偶剧场管理

解题思路

这是一道模拟题，核心是矩形窗口的遮挡计算。操作本身（增删改查窗口属性）都是常规的模拟，难点在于 queryVisibility 和 queryAllVisibleWindows 两个查询操作。

优先级规则

窗口遮挡优先级：level 大的在上；level 相同则后创建的在上。用 (level, 创建序号) 的二元组即可比较。

可见性判断

一个窗口的可见区域 = 自身矩形 ∩ 舞台边界 − 所有更高优先级窗口的矩形。

关键操作是矩形相减：从矩形 A 中挖掉矩形 B 覆盖的部分。若 A 和 B 有重叠，将 A 切割为最多 4 个不重叠的子矩形（上/下/左/右四条边条）：

┌──────────┐
│   top     │
├────┬─────┤
│left│ B   │right
├────┴─────┤
│  bottom   │
└──────────┘

用列表维护当前剩余矩形集合，依次用每个更高优先级窗口去减即可。

queryAllVisibleWindows

对查询区域 Q 内的每个窗口 W：

1. 取 W ∩ Q 作为候选区域
2. 用所有比 W 优先级高的窗口依次相减
3. 若剩余面积 > 0，则 W 在 Q 内可见

最后按 level 降序、名称字典序排列输出。

代码实现

def clip(x1, y1, x2, y2):
    """裁剪到舞台范围内"""
    x1, y1 = max(x1, 0), max(y1, 0)
    x2, y2 = min(x2, SW), min(y2, SH)
    if x1 >= x2 or y1 >= y2:
        return None
    return (x1, y1, x2, y2)


def sub_rect(rects, hole):
    """从 rects 中所有矩形减去 hole"""
    if hole is None:
        return rects
    hx1, hy1, hx2, hy2 = hole
    res = []
    for x1, y1, x2, y2 in rects:
        # 无重叠
        if x2 <= hx1 or x1 >= hx2 or y2 <= hy1 or y1 >= hy2:
            res.append((x1, y1, x2, y2))
            continue
        # 切割出上下左右四条
        if y1 < hy1:
            res.append((x1, y1, x2, hy1))       # top
        if y2 > hy2:
            res.append((x1, hy2, x2, y2))       # bottom
        if x1 < hx1:
            res.append((x1, max(y1, hy1), hx1, min(y2, hy2)))  # left
        if x2 > hx2:
            res.append((hx2, max(y1, hy1), x2, min(y2, hy2)))  # right
    return res


def visible_area(x1, y1, x2, y2, higher_windows):
    """计算 (x1,y1,x2,y2) 被 higher_windows 遮挡后的剩余矩形列表"""
    r = clip(x1, y1, x2, y2)
    if r is None:
        return []
    rects = [r]
    for hw in higher_windows:
        hole = clip(hw['x'], hw['y'], hw['x'] + hw['w'], hw['y'] + hw['h'])
        rects = sub_rect(rects, hole)
    return rects


SW = SH = 0
wins = {}  # name -> window dict
order = 0


def process(line):
    global SW, SH, order
    parts = line.split()
    cmd = parts[0]

    if cmd == 'init':
        W, H = int(parts[1]), int(parts[2])
        if W <= 0 or H <= 0:
            return 'false'
        SW, SH = W, H
        return 'true'

    if cmd == 'createWindow':
        name = parts[1]
        x, y = int(parts[2]), int(parts[3])
        if len(parts) == 7:
            w, h, level = int(parts[4]), int(parts[5]), int(parts[6])
        else:
            size = int(parts[4])
            w = h = size
            level = int(parts[5])
        if name in wins or w <= 0 or h <= 0:
            return 'false'
        order += 1
        wins[name] = {'x': x, 'y': y, 'w': w, 'h': h, 'level': level, 'idx': order}
        return 'true'

    if cmd == 'removeWindow':
        name = parts[1]
        if name not in wins:
            return 'false'
        del wins[name]
        return 'true'

    if cmd == 'resize':
        name, nw, nh = parts[1], int(parts[2]), int(parts[3])
        if name not in wins or nw <= 0 or nh <= 0:
            return 'false'
        wins[name]['w'], wins[name]['h'] = nw, nh
        return 'true'

    if cmd == 'move':
        name, nx, ny = parts[1], int(parts[2]), int(parts[3])
        if name not in wins:
            return 'false'
        wins[name]['x'], wins[name]['y'] = nx, ny
        return 'true'

    if cmd == 'queryVisibility':
        name = parts[1]
        if name not in wins:
            return 'false'
        w = wins[name]
        pri = (w['level'], w['idx'])
        higher = [v for v in wins.values() if (v['level'], v['idx']) > pri]
        rects = visible_area(w['x'], w['y'], w['x'] + w['w'], w['y'] + w['h'], higher)
        return 'true' if rects else 'false'

    if cmd == 'queryAllVisibleWindows':
        qx, qy, qw, qh = int(parts[1]), int(parts[2]), int(parts[3]), int(parts[4])
        result = []
        for name, w in wins.items():
            pri = (w['level'], w['idx'])
            higher = [v for v in wins.values() if (v['level'], v['idx']) > pri]
            rects = visible_area(
                max(w['x'], qx), max(w['y'], qy),
                min(w['x'] + w['w'], qx + qw), min(w['y'] + w['h'], qy + qh),
                higher
            )
            if rects:
                result.append((-w['level'], name))
        if not result:
            return 'NoVisibleWindow'
        result.sort(key=lambda x: (x[0], x[1]))
        return ';'.join(name for _, name in result)


import sys
for line in sys.stdin:
    line = line.strip()
    if line:
        print(process(line))

代码解析

以示例为例，移除 window2 后舞台上剩 window1 和 window3：

window1: (10,10) 100×100 level=1
window3: (70,90) 50×50  level=3

queryVisibility window1：window1 被 window3 遮挡了 100×50 的重叠区域，但剩余面积 = 10000 − 1500 > 0，可见 → true。

queryAllVisibleWindows(10,10,100,100)：查询区域 [10,110]×[10,110]。

• window3（level=3）在区域内有可见部分 → 入选
• window1（level=1）被 window3 遮挡后仍有剩余 → 入选
• 按 level 降序排列：window3 在前 → window3;window1

矩形相减的核心：sub_rect 函数。每减一个遮挡矩形，将剩余部分切成至多 4 个小矩形。多个遮挡窗口依次相减，最终列表非空则可见。操作总数 ≤ 100，每个查询最多 100 个窗口做相减，每次相减最多产生 4 个子矩形，计算量完全可控。

复杂度分析

• 时间复杂度：每次查询 O(n² × 矩形切割开销)，n ≤ 100，足够
• 空间复杂度：O(n) 存窗口 + O(n) 矩形列表