【題解】Luogu P1003 【铺地毯】

首先看题被分类迷惑了,以为可以直接暴力模拟,创一个一百万乘一百万的二维数组。然后发现。。。不用想128MB绝对放不下,128MB大概开5700×5700的二维int数组,就算是short也不够。

所以这题就不能陷入思维怪圈。

然后我们就可以想一个数学方法,即判断一个点是否在一个正方形内(不妨令点坐标为(px,py),正方形左下角坐标(a,b),大小为s),则有

px >= a
px <= a + s
py >= b
py <= b + s

恒成立
然后我们就只需倒着遍历地毯(如果你是顺着读入的话),然后判断即可

如何输入就在此不述了

    #include<cstdio>
    using namespace std;
    int carpet[10000][5] = {};
    int main(){
        int n;
        scanf("%d",&n);
        for(int i = 0;i < n;i++){
            scanf("%d %d %d %d",&carpet[i][0],&carpet[i][1],&carpet[i][2],&carpet[i][3]);
            carpet[i][4] = i + 1;
        }
        int px,py;
        scanf("%d %d",&px,&py);
        int result = -1;
        for(int i = n - 1;i >= 0;i--){
            if(px >= carpet[i][0] && px <= carpet[i][0] + carpet[i][3] && py >= carpet[i][1] && py <= carpet[i][1] + carpet[i][3]){
                result = carpet[i][4];
                break;
            }
        }
        printf("%d",result);
        return 0;
}