【洛谷P1003 铺地毯】蒟蒻题解

后铺的地毯要比先铺的位置要更靠上，所以倒着循环的，从最后铺的地毯开始查找，查找$(x,y)$这个点是不是在这张地毯的范围内，然后按照题目要求输出即可。

原题：传送门

本蒟蒻的题解，让大神们见笑了！
从上图，大家可以发现一点：后铺的地毯要比先铺的位置要更靠上，这点很重要。
$OK$，开始进入代码讲解。

#include<iostream>
using namespace std;
int a[10001],b[10001],g[10001],k[10001],n,i,j,d,x,y;
int main()
{
	cin>>n;
	for(d=1;d<=n;d++)
		cin>>a[d]>>b[d]>>g[d]>>k[d];
	cin>>x>>y;

输入部分没什么可以讲的，咋们就跳过了。

for(d=n;d>=1;d--)
		if(x>=a[d]&&x<=g[d]+a[d]&&y>=b[d]&&y<=k[d]+b[d])
		{
			cout<<d;
			return 0;
		}

（敲黑板）接下来是重点，注意看哦。
有的眼尖的朋友可能会发现：我是倒着循环的，这是一个涉及到贪心的一个小技巧，前面我们也讲到了，后铺的地毯要比先铺的位置要更靠上，那么，从最后铺的地毯开始查找，会更省时间。
然后呢，其实就是查找$(x,y)$这个点是不是在这张地毯的范围内，如果是，则直接输出这张地毯的编号，然后$return$就行了。

cout<<"-1";
	return 0;
}

如果$(x,y)$这个点上并没有地毯，那么直接输出“$-1$”，表示：这个$(x,y)$点上没有铺过地毯。
完整代码如下：

#include<iostream>
using namespace std;
int a[10001],b[10001],g[10001],k[10001],n,i,j,d,x,y;
int main()
{
	cin>>n;
	for(d=1;d<=n;d++)
		cin>>a[d]>>b[d]>>g[d]>>k[d];
	cin>>x>>y;
	for(d=n;d>=1;d--)
		if(x>=a[d]&&x<=g[d]+a[d]&&y>=b[d]&&y<=k[d]+b[d])
		{
			cout<<d;
			return 0;
		}
	cout<<"-1";
	return 0;
}