华为 · 计算几何 · 算法编程题
华为 计算几何 时限 2 秒 / 256 MB

题目描述

人偶师爱丽丝正在布置一场人偶剧。她在舞台(屏幕)上划分了若干个矩形区域作为不同人偶的活动范围,并称之为“窗口”。
舞台是一个左上角坐标为 (0,0) ,右下角坐标为 (W, H) 的矩形区域。每个窗口具有唯一的名称、位置 (x, y) 、尺寸 (w, h) 以及层级 level 。
窗口之间的遮挡关系遵循以下优先级:
1. 层级优先: level 较大的窗口位于 level 较小的窗口之上。
2. 时序次之:若两个窗口 level 相同,则后创建(操作序列中位置靠后)的窗口位于先创建的窗口之上。
一个窗口的可见部分定义为:该窗口在舞台边界 [0, W] × [0, H] 之内,且未被任何优先级更高的窗口遮挡的区域。若一个窗口的可见部分面积大于 0 ,则称该窗口是可见的。
爱丽丝需要你实现一个系统,处理一系列对舞台和窗口的操作。

输入输出

输入描述
输入包含若干行,每行一个操作。操作总数不超过 100 个。
所有坐标、宽度、高度均为 32 位带符号整数。窗口名称仅包含英文字母且不含空格。
1. `init W H`:初始化舞台大小为 W × H 。若 W ≤ 0 或 H ≤ 0 ,初始化失败返回 `false`;否则返回 `true`。若初始化失败,后续将无任何操作。
2. `createWindow name x y w h level` 或 `createWindow name x y size level`:创建一个窗口。
- 若参数为 5 个整数,则宽度为 w ,高度为 h 。
- 若参数为 4 个整数,则宽度和高度均为 size 。
- 若 w, h ≤ 0 或名称已存在,返回 `false`;否则返回 `true`。
3. `removeWindow name`:移除名称为 `name` 的窗口。若窗口不存在返回 `false`,否则返回 `true`。
4. `resize name newW newH`:将指定窗口的尺寸更改为 newW × newH 。若窗口不存在或 newW, newH ≤ 0 ,返回 `false`,否则返回 `true`。
5. `move name newX newY`:将指定窗口的左上角移动至 (newX, newY) 。若窗口不存在返回 `false`,否则返回 `true`。
6. `queryVisibility name`:查询窗口 `name` 是否可见。可见返回 `true`,否则(或窗口不存在)返回 `false`。
7. `queryAllVisibleWindows x y w h`:在指定的矩形区域 Q = [x, x+w] × [y, y+h] 内,按优先级从高到低列出所有可见面积大于 0 的窗口名称。
- 排序规则:首先按 level 降序排列,若 level 相同按名称的字典序升序排列。
- 输出格式:名称之间用分号 `;` 分隔。若区域内无可见窗口,输出 `NoVisibleWindow`。
输出描述
对每个操作,输出其对应的返回值(`true`、`false` 或字符串)并换行。

样例共 1 组

样例 1 · 1. `init 200 300` 创建了 200 × 300 的舞台。 2. `window1`, `window2`, `window3` 相继被成功创建。 3. `window2` 被成功移除;移除不存在的 `window4` 失败返回 `false`。 4. `window1` 虽然被 `window3` 部分遮挡,但仍有剩余可见面积,故返回 `true`。 5. 在查询区域 [10, 10] × [110, 110] 中,`window3` 和 `window1` 均有可见部分。由于 `window3` 的 level=3 大于 `window1` 的 level=1 ,故先输出 `window3`。
输入
init 200 300
createWindow window1 10 10 100 100 1
createWindow window2 20 20 40 30 2
createWindow window3 70 90 50 3
removeWindow window2
removeWindow window4
queryVisibility window1
queryAllVisibleWindows 10 10 100 100
输出
true
true
true
true
true
false
true
window3;window1

算法解析依据一般

考点:计算几何

限制 2 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:2 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:计算几何

把几何关系转成坐标运算,用整数运算避免浮点误差。

思路框架(计算几何 通法 · 非本题专属)

  1. 把点、向量、线段用坐标表示。
  2. 几何判定(平行、垂直、共线、相交)尽量用叉积/点积的整数形式:叉积为 0 即共线。
  3. 距离用平方比较,避免开方带来的浮点误差。
  4. 面积用叉积(鞋带公式)计算。

实现要点:叉积 cross = x1*y2 - x2*y1;用它判断顺时针/逆时针和共线。

复杂度:时间 O(n) ~ O(n²) | 空间 O(n)

该范式的通法易错点

  • 用浮点相等判断几何关系(应用整数叉积)。
  • 没考虑三点共线、重合等退化情况。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例解读

样例 1:输入 init 200 300 / createWindow window1 10 10 100 100 1 / createWindow window2 20 20 40 30 2 / createWin → 输出 true / true / true / true / true / false / true / window3;window1

  1. init 200 300 创建了 200 × 300 的舞台。
  2. window1, window2, window3 相继被成功创建。
  3. window2 被成功移除;移除不存在的 window4 失败返回 false
  4. window1 虽然被 window3 部分遮挡,但仍有剩余可见面积,故返回 true
  5. 在查询区域 [10, 10] × [110, 110] 中,window3window1 均有可见部分。由于 window3 的 level=3 大于 window1 的 level=1 ,故先输出 window3

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2026年-华为-04月15号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解