题目
在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 n 张地毯,编号从 1 到 n。
现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后,求覆盖地面某个点的最上面的那张地毯的编号。
注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
解题思路
第 i 张地毯的左下角点坐标为 (c[i][0], c[i][1]),右上角点坐标为 (c[i][2], c[i][3])。
从第 n 张地毯遍历到第 1 张,如果地毯覆盖在所求的点 (x,y) 上,则这张地毯是最上面的地毯,记录下编号,退出循环。
C++代码
#include<cstdio>
#include<vector>
using namespace std;
int main(){
int n;
scanf("%d", &n);
vector<vector<int>> c(n, vector<int>(4));
for(int i=0; i<n; ++i){
scanf("%d%d%d%d", &c[i][0], &c[i][1], &c[i][2], &c[i][3]);
c[i][2] += c[i][0];
c[i][3] += c[i][1];
}
int x, y;
scanf("%d%d", &x, &y);
int ans = -1;
for(int i=n-1; i>=0; --i){
if(x>=c[i][0] && x<=c[i][2] && y>=c[i][1] && y<=c[i][3]){
ans = i+1;
break;
}
}
printf("%d\n", ans);
return 0;
}
京公网安备 11010502036488号