P1003 铺地毯
题意描述
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 11 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入格式 输入共 n + 2 行。
第一行，一个整数 n，表示总共有 n 张地毯。
接下来的 n 行中，第i+1 行表示编号 ii 的地毯的信息，包含四个正整数 a ,b ,g ,k每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 (a, b)以及地毯在 x 轴和 y 轴方向的长度。
第 n + 2行包含两个正整数 x 和y，表示所求的地面的点的坐标 (x,y)。
输出格式 输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。
思路
最开始我想的是用map来存从起点到终点所有地毯的编号，但只得了一半的分，内存超了。然后想到保存每轮地毯的起点和终点，最后逆序遍历，如果覆盖了地毯，直接输出，否则输出-1
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef long long LL;
const int N=1e4+10;
int ans[N][4];
int n;
int main(){
IOS;
cin>>n;
int m=0;
int t=1;
for(int i=1;i<=n;i++){
int a,b,g,k;
cin>>a>>b>>g>>k;
ans[i][1]=a;
ans[i][2]=b;
ans[i][3]=a+g;
ans[i][4]=b+k;
}
int x,y;cin>>x>>y;
for(int i=n;i>=1;i--){
if(x>=ans[i][1]&&y>=ans[i][2]&&x<=ans[i][3]&&y<=ans[i][4]){
cout<<i<<endl;
return 0;
}
}
cout<<-1<<endl;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-03-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录