题目
在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 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; }