当前位置: 代码迷 >> 综合 >> P1003 铺地毯(模拟)
  详细解决方案

P1003 铺地毯(模拟)

热度:46   发布时间:2024-01-25 11:59:58.0

题意

n n 个大小不同的矩形按顺序覆盖,求某一个坐标点最后覆盖的矩形是谁。

题解

我们考虑由于是最后一个覆盖的矩形,所以我们可以从后向前枚举。这样第一个覆盖这个点的矩形一定是最后覆盖的矩形。
然后只需要枚举的时候判断这个点在不在矩形里了。

代码

#include<iostream>
using namespace std;
struct Rec
{int x,y,n,m;
}rec[10000+10];
int main()
{int n;cin>>n;for(int i=1;i<=n;++i)cin>>rec[i].n>>rec[i].m>>rec[i].x>>rec[i].y;int x,y;cin>>x>>y;int ans=-1;for(int i=n;i>=1;--i){if(rec[i].n<=x && rec[i].m<=y){if(rec[i].n+rec[i].x>=x && rec[i].m+rec[i].y>=y){ans=i;break;}}}cout<<ans<<endl;return 0;
}