包含必要的头文件：
- 引入 <iostream> 进行输入输出操作，<vector> 用于存储地毯信息。
定义 Carpet 结构体：
- 存储地毯的左下角坐标（a，b）以及在 x 和 y 方向的长度（g，k）。
读取地毯数量：
- 输入整数 n，表示地毯的数量，并创建一个大小为 n + 1 的 carpets 向量（使用 1-based 索引）。
读取每张地毯的信息：
- 从第 1 张到第 n 张，循环读取每张地毯的详细信息，存储在 carpets 向量中。
读取查询点的坐标：
- 输入需要查询的点的坐标 x 和 y。
初始化结果变量：
- 将 topCarpet 初始化为 -1，表示该点未被任何地毯覆盖。
从上到下检查地毯：
- 从最后铺设的地毯（编号最大的地毯）开始，向前遍历。
- 计算当前地毯的边界：左边界 left，右边界 right，下边界 bottom，上边界 top。
- 检查点 (x, y) 是否在当前地毯的范围内（包括边界）。
- 如果在范围内，更新 topCarpet 为当前地毯的编号 i，并退出循环。
输出结果：
- 输出 topCarpet 的值，如果点被某张地毯覆盖，则输出其编号；否则输出 -1。

代码实现：

/**************************************************************** 
 * Description: 2011年提高组第一题 铺地毯
 * Author: Alex Li
 * Date: 2024-10-11 16:46:04
 * LastEditTime: 2024-10-11 16:46:12
****************************************************************/
#include <iostream>
#include <vector>
using namespace std;

// 定义一个结构体来存储地毯信息
struct Carpet {
    int a; // 地毯左下角的 x 坐标
    int b; // 地毯左下角的 y 坐标
    int g; // 地毯在 x 方向的长度
    int k; // 地毯在 y 方向的长度
};

int main() {
    int n; // 地毯的数量
    cin >> n;

    // 创建一个向量来存储所有地毯的信息，使用 1-based 索引方便处理
    vector<Carpet> carpets(n + 1);

    // 读取每张地毯的信息
    for (int i = 1; i <= n; ++i) {
        cin >> carpets[i].a >> carpets[i].b >> carpets[i].g >> carpets[i].k;
    }

    int x, y; // 查询点的坐标
    cin >> x >> y;

    int topCarpet = -1; // 初始化结果为 -1，表示未被任何地毯覆盖

    // 从最上层的地毯开始检查
    for (int i = n; i >= 1; --i) {
        // 获取当前地毯的边界
        int left = carpets[i].a;
        int right = carpets[i].a + carpets[i].g;
        int bottom = carpets[i].b;
        int top = carpets[i].b + carpets[i].k;

        // 检查点 (x, y) 是否在当前地毯范围内（包括边界）
        if (x >= left && x <= right && y >= bottom && y <= top) {
            topCarpet = i; // 找到了覆盖该点的最上层地毯
            break; // 不再需要继续检查
        }
    }

    cout << topCarpet << endl; // 输出结果

    return 0;
}

Previous Topic

Back to Lesson

Next Topic