铺地毯

题目描述

平面上按 $1\sim n$ 顺序铺上 $n$ 张与坐标轴平行的矩形地毯，后铺的覆盖在先铺的上面。第 $i$ 张地毯左下角为 $(a_i,b_i)$ ， $x$ 方向长 $g_i$ 、 $y$ 方向长 $k_i$ （含边界）。给定查询点 $(x,y)$ ，输出覆盖该点的最上面那张地毯编号；若没有则输出 $-1$ 。

思路

查询点只有一个，倒序检查每张地毯，第一个满足 $a_i\le x\le a_i+g_i$ 且 $b_i\le y\le b_i+k_i$ 的即为答案；全不满足则输出 $-1$ 。

参考代码

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#!/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-10-02 09:30
# update_at: 2026-10-02 09:30

import sys


def cover(x: int, y: int, a: int, b: int, g: int, k: int) -> bool:
    """点 (x, y) 是否在地毯 [a, a+g] × [b, b+k] 内（含边界）。"""
    return a <= x <= a + g and b <= y <= b + k


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    # 按铺设顺序存下每张地毯；从最后一张往前找，第一个覆盖查询点的就是最上面的。
    carpets = [(next(data), next(data), next(data), next(data)) for _ in range(n)]
    x, y = next(data), next(data)

    for i in range(n - 1, -1, -1):
        a, b, g, k = carpets[i]
        if cover(x, y, a, b, g, k):
            print(i + 1)  # 地毯编号从 1 开始
            return
    print(-1)


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/**
 * 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 14:42
 * update_at: 2026-10-06 14:42
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 10005;

struct Carpet {
    ll a, b, g, k; // 左下角 (a,b)，x 方向长 g，y 方向长 k
} carpets[MAXN];

int n;
ll xq, yq; // 查询点

// 第 i 张地毯是否覆盖查询点（含边界）
bool cover(int i) {
    return carpets[i].a <= xq && xq <= carpets[i].a + carpets[i].g &&
           carpets[i].b <= yq && yq <= carpets[i].b + carpets[i].k;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld %lld %lld %lld", &carpets[i].a, &carpets[i].b, &carpets[i].g, &carpets[i].k);
    }
    scanf("%lld %lld", &xq, &yq);

    // 后铺的在上，倒序找第一个覆盖查询点的地毯
    for (int i = n; i >= 1; --i) {
        if (cover(i)) {
            printf("%d\n", i);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

目录

题目描述

思路

参考代码