Windows ACM

### Windows ACM - 窗口选择问题解析 #### 背景介绍 在计算机桌面管理领域，特别是对于那些不习惯于频繁整理桌面的应用程序窗口的用户来说，如何准确地识别并选择位于屏幕特定位置的窗口是一项有趣且实用的技术挑战。本问题通过一个具体的场景——Emma的桌面管理混乱情况，来探讨一种算法解决方案。 #### 问题描述 Emma 的电脑桌面上布满了各种应用程序窗口，这些窗口可能重叠在一起，也可能完全被其他窗口遮挡。给定每个窗口的左上角坐标、宽度和高度以及一系列屏幕上的点击位置，任务是确定每次点击时选中的窗口（如果有）。 #### 输入格式 输入由多个测试用例组成。每个测试用例首先包含一个整数 \( n \)，表示桌面上打开的窗口数量（\( 1 \leq n \leq 100 \)）。接下来有 \( n \) 行，每行包含四个整数 \( r, c, w, h \)，分别表示第 \( i \) 个窗口左上角的行坐标 \( r \) 和列坐标 \( c \) （\( 0 \leq r, c \leq 999999 \)），以及窗口的宽度 \( w \) 和高度 \( h \)（\( 1 \leq w, h \leq 1000000 \)）。然后是一个整数 \( m \)，表示查询次数（\( 1 \leq m \leq 100 \)），接着有 \( m \) 行，每行包含两个整数 \( cr, cc \)，分别表示点击的行坐标和列坐标。 #### 输出格式 对于每个测试用例，输出应包括该测试用例的编号，然后是 \( m \) 行，每行对应一个查询结果。如果点击的位置落在某个窗口内，则输出“window k”，其中 \( k \) 是窗口的编号；否则输出“background”。窗口按打开顺序编号，第一个打开的窗口编号为 1。 #### 样例输入与输出解释 - **样例输入**： ```plaintext 3 1 2 3 3 2 3 2 2 3 4 2 2 4 3 5 1 2 4 2 3 3 2 5 10 2 10 100 100 100 100 2 5 13 100 101 0 ``` - **样例输出**： ```plaintext Desktop 1: window 3 window 1 background window 2 Desktop 2: background window 2 ``` #### 解析 为了处理这个问题，可以采用如下的步骤： 1. **读取数据**：根据输入格式，读取每个测试用例的数据。 2. **定义结构体**：创建两个结构体 `Window` 和 `Query` 分别用于存储窗口的信息（左上角坐标、宽度和高度）和点击位置（行坐标和列坐标）。 3. **遍历查询**：对于每个查询，遍历所有窗口，检查点击位置是否落在任一窗口内。 - 如果点击位置落在某窗口内，则记录该窗口编号。 - 如果遍历完所有窗口仍未找到，则点击位置落在背景上。 4. **输出结果**：按照指定格式输出每个查询的结果。 #### 算法实现 在提供的代码片段中，可以看到主要的实现逻辑。程序使用了两个结构体 `Window` 和 `Query` 来存储窗口信息和查询信息，并使用了嵌套循环来匹配查询位置和窗口。对于每个查询，程序从最后一个打开的窗口开始检查，这确保了即使窗口重叠也能正确地找到最顶层的窗口。 #### 结论 通过上述方法，我们成功解决了这一桌面窗口选择问题，实现了准确判断点击位置所对应的窗口或背景的功能。这种算法不仅适用于本问题，也可以扩展到更复杂的桌面管理场景中。