[已解决]梦想护卫舰 第19关 铺地毯

元豪

上一关：解密

梦想护卫舰 第19关 铺地毯

你们进入外星人领地后，外星人说：“你们把我们的难题解开，我就放了他。”（外星人事先准备好了翻译器）

外星人的难题是这样的：

外星人为了准备一个独特的颁奖典礼，他们在会场的一片矩形区域铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，外星人想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

为了救出zhangjinxuan，你们只好绞尽脑汁的解题。

                               
登录/注册后可看大图

输入格式

输入共 n + 2 行。

第一行，一个整数 n，表示总共有 n 张地毯。

接下来的 n 行中，第 i+1 行表示编号 i 的地毯的信息，包含四个整数 a、b、g、k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 (a, b) 以及地毯的长和宽

第 n + 2 行包含两个整数 x 和 y，表示所求的地面的点的坐标 x, y。

输出格式

输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。

输入输出样例

输入 #1

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

输出 #1

3

输入 #2

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

输出 #2

-1

数据范围

对于 100% 的数据，有 0 ≤ n ≤ 10^4 , 0 ≤ a、b、g、k ≤ 10^5。

时间限制  1.00s

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

                               
登录/注册后可看大图

答题规则
1. 不能抄题解，否则无奖励，可能还会扣分;
2. 爆零的代码，视为普通回帖，不会奖励；
3. 语言任意。
4. 当您遇到问题时，您可以回贴提问，我会为您解答

奖励规则
1. 奖励3天后统一发，3天内发布的题解才有效；
2. 提供完整题解，但没有上排行榜，奖励1鱼币+1荣誉；
3. 高于1鱼币1荣誉的奖励，仅给排行榜上的鱼油（因为经济原因，请谅解）；
4. 因为额度原因，部分鱼油可能下一天才能奖励。

                               
登录/注册后可看大图

排行榜

	第一名	第二名	第三名
名字
链接
语言
得分

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2023-2-3 11:46:34

#include<bits/stdc++.h>
using namespace std;

int n, a[10001], b[10001], g[10001], k[10001], x, y;

int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
                scanf("%d%d%d%d", &a[i], &b[i], &g[i], &k[i]);
                g[i] += a[i];
                k[i] += b[i];
        }
        scanf("%d%d", &x, &y);
        for (int i = n; i >= 1; --i) {
                if (x >= a[i] && x <= g[i] && y >= b[i] && y <= k[i]) {
                        printf("%d\n", i);
                        return 0;
                }
        }
        puts("-1");
    return 0;
}

跳转到最佳答案楼层

元豪

@高山 @zhangjinxuan @tommyyu @sfqxx @python爱好者. @liuhongrun2022

高山

很厉害哈，不错啊。

元豪

高山 发表于 2023-2-3 10:49
很厉害哈，不错啊。

sfqxx

支持(领鱼币)

zhangjinxuan

好奇你是怎么做的

鱼cpython学习者

写了个最简单的

n = int(input())
rect = []
for _ in range(n):
    rect.append([int(i) for i in input().split(' ')])
point = [int(i) for i in input().split(' ')]
for index, item in enumerate(rect[::-1]):
    if point[0] - item[0] <= item[2] and point[1] - item[1] <= item[3]:
        print(n - index)
        break
else:
    print(-1)

希望无bug

元豪

鱼cpython学习者 发表于 2023-2-3 11:26
写了个最简单的

希望无bug

很遗憾，只有30分

元豪

zhangjinxuan 发表于 2023-2-3 11:26
好奇你是怎么做的

你不会吗

鱼cpython学习者

元豪 发表于 2023-2-3 11:32
很遗憾，只有30分

我好像知道怎么回事了
我比较那里忘了限差是正数

zhangjinxuan

元豪 发表于 2023-2-3 11:33
你不会吗

这个我琢磨了很久才做出来

元豪

zhangjinxuan 发表于 2023-2-3 11:36
这个我琢磨了很久才做出来

我看了一下你的记录，你得了50分是吧

zhangjinxuan

元豪 发表于 2023-2-3 11:37
我看了一下你的记录，你得了50分是吧

琢磨很久，90

zhangjinxuan

元豪 发表于 2023-2-3 11:37
我看了一下你的记录，你得了50分是吧

啊似的是的，我不会，我不会
现在我要自己琢磨出来

元豪

zhangjinxuan 发表于 2023-2-3 11:39
啊似的是的，我不会，我不会
现在我要自己琢磨出来

加油！提示一下：
后面的毯子会把前面的覆盖

鱼cpython学习者

元豪 发表于 2023-2-3 11:32
很遗憾，只有30分

可以改代码吗

zhangjinxuan

#include<bits/stdc++.h>
using namespace std;

int n, a[10001], b[10001], g[10001], k[10001], x, y;

int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
                scanf("%d%d%d%d", &a[i], &b[i], &g[i], &k[i]);
                g[i] += a[i];
                k[i] += b[i];
        }
        scanf("%d%d", &x, &y);
        for (int i = n; i >= 1; --i) {
                if (x >= a[i] && x <= g[i] && y >= b[i] && y <= k[i]) {
                        printf("%d\n", i);
                        return 0;
                }
        }
        puts("-1");
    return 0;
}

元豪

鱼cpython学习者 发表于 2023-2-3 11:43
可以改代码吗

可以

元豪

zhangjinxuan 发表于 2023-2-3 11:46

恭喜通过~

鱼cpython学习者

元豪 发表于 2023-2-3 11:46
可以

n = int(input())
rect = []
for _ in range(n):
    rect.append([int(i) for i in input().split(' ')])
point = [int(i) for i in input().split(' ')]
for index, item in enumerate(rect[::-1]):
    if 0 <= point[0] - item[0] <= item[2] and 0 <= point[1] - item[1] <= item[3]:
        print(n - index)
        break
else:
    print(-1)