铺地毯

题目描述

$n$ 张矩形地毯按编号 $1 \sim n$ 先后平行于坐标轴铺设，后铺的覆盖在先铺的之上。第 $i$ 张地毯由左下角 $(a_i, b_i)$ 及 $x$ 、 $y$ 方向长度 $g_i$ 、 $k_i$ 描述。给定点 $(x, y)$ ，求盖住它的最上面一张地毯的编号，没有则输出 -1；边界和顶点上的点也算被覆盖。

输入：第一行整数 $n$ ；接下来 $n$ 行每行四个正整数 $a_i, b_i, g_i, k_i$ ；最后一行两个正整数 $x, y$ 。输出：一行，一个整数表示地毯编号，未被覆盖输出 -1。 样例输入：3 / 1 0 2 3 / 0 2 3 3 / 2 1 3 3 / 2 2，样例输出：3。

思路

地毯是闭矩形，第 $i$ 张盖住 $(x,y)$ 当且仅当 $a_i \le x \le a_i+g_i$ 且 $b_i \le y \le b_i+k_i$ 。「后铺的在上」等价于覆盖该点的地毯中编号最大者获胜，因此从 $n$ 号倒序枚举，遇到的第一张满足判定的地毯就是答案，一张都没有则输出 $-1$ 。只有一个询问点，直接 $O(n)$ 扫描即可。

参考代码

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#!/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-09-29 19:38
# update_at: 2026-09-29 19:38

import sys


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)

    # 编号大的是后铺的，覆盖在上面：从后往前找到第一张盖住 (x, y) 的地毯即答案。
    # 盖住 = a <= x <= a+g 且 b <= y <= b+k（边界上的点也算被覆盖）。
    ans = next(
        (i for i in range(n, 0, -1) if (a := carpets[i - 1][0]) <= x <= a + carpets[i - 1][2]
            and (b := carpets[i - 1][1]) <= y <= b + carpets[i - 1][3]),
        -1,  # 一张都没盖住
    )

    print(ans)


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-05 02:25
 * update_at: 2026-10-05 02:25
 */

#include <cstdio>

// 地毯数量上限（题面 n 张，编号 1~n）
const int MAXN = 100005;

int ax[MAXN]; // ax[i] 第 i 张地毯左下角的 x 坐标
int ay[MAXN]; // ay[i] 第 i 张地毯左下角的 y 坐标
int gx[MAXN]; // gx[i] 第 i 张地毯在 x 方向的长度
int gy[MAXN]; // gy[i] 第 i 张地毯在 y 方向的长度

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d %d %d %d", &ax[i], &ay[i], &gx[i], &gy[i]);
    }

    int x, y;
    scanf("%d %d", &x, &y);

    // 后铺的盖在先铺的之上，等价于覆盖该点的地毯中编号最大者获胜。
    // 于是从 n 号倒序枚举，遇到第一张闭矩形覆盖 (x, y) 的地毯就是答案。
    int ans = -1;
    for (int i = n; i >= 1; --i) {
        // 闭矩形判定：边界和顶点上的点也算被覆盖
        if (ax[i] <= x && x <= ax[i] + gx[i] && ay[i] <= y && y <= ay[i] + gy[i]) {
            ans = i;
            break;
        }
    }

    printf("%d\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码