铺地毯

GitHub跳转原题关系图返回列表

题意与原解析均从本地 OpenJudge 缓存迁移。

OJ: noi_openjudge

题目 ID: ch0109-14

难度:未知

标签:模拟枚举几何python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
  5. C++代码
    1. 复杂度
    2. 总结

题意

完整题面见同目录的 problem.md。

思路

倒序检查地毯，第一张覆盖查询点的地毯即为最上层。

代码

Python代码

python
carpet_count = int(input())
carpets = [tuple(map(int, input().split())) for _ in range(carpet_count)]
x, y = map(int, input().split())
for index in range(carpet_count - 1, -1, -1):
    left, bottom, width, height = carpets[index]
    if left <= x <= left + width and bottom <= y <= bottom + height:
        print(index + 1)
        break
else:
    print(-1)

C++代码

cpp
#include <cstdio>

int n;
struct _a{
    int x1,y1,x2,y2;
}a[10005];
int x,y;
int main(){
    scanf("%d",&n);
    int i,j;

    int ans = -1;
    for(i=1;i<=n;i++){
        scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
    }
    scanf("%d%d",&x,&y);
    for(i=n;i>=1;i--){
        if(a[i].x1 <= x && (a[i].x1+ a[i].x2) >= x && a[i].y1 <= y && (a[i].y1+a[i].y2)>= y){
            ans = i;
            break;
        }
    }


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

复杂度

总结