#洛谷模拟系列#

就是对数据要求不同的时候分类处理(雾)

题目描述

为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 nnn 张地毯,编号从 111 到nnn。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入输出格式

输入格式:

 

输入共n+2行

第一行,一个整数n,表示总共有n张地毯

接下来的n行中,第 i+1行表示编号iii的地毯的信息,包含四个正整数a,b,g,k ,每两个整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标(a,b)以及地毯在x轴和y轴方向的长度

第n+2行包含两个正整数x和y,表示所求的地面的点的坐标(x,y)

 

输出格式:

 

输出共1行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出−1

/——————————————————————清爽的分割线——————————————————————————————/

我已经试过了,用莽涂色的方法肯定RE,但是有个东西很神奇,叫数学,代码如下

#RE神器#

 1 #include<stdio.h>
 2 /*思路:
 3     按照上色的方式,开一个二维数组,对于不同编号的毯子所覆盖的区域
 4     编号(上色),直接输出结果
 5 */
 6 
 7 
 8 /*------针对小数据的方法-------大数据必RE*/
 9 
10 #define MAXSIZE 50
11 int ground[MAXSIZE][MAXSIZE] = {{0}};
12 void paint(int id,int x,int y,int width_x,int lenth_y)
13 {
14     int i = 0,j = 0;
15     //参数行里面分别是毯子的编号,左下角的坐标,宽度,长度
16     //注意,数组的坐标方向与实际的坐标方向不同,即左下角-->左上角
17     //在更换了坐标方向之后,原本由左下向右上的扩充就变为了左上到右下
18     //判断是否出界啊
19     for(i = y;i < y + lenth_y && i < MAXSIZE;i++)
20         for(j = x;j < x + width_x && j < MAXSIZE;j++)
21         {
22             ground[i][j] = id;
23         }
24         
25 }
26 int main()
27 {
28     int num,t;
29     int x,y,width_x,lenth_y;
30     int check_x,check_y;
31     scanf("%d",&num);
32     
33     for(t = 1;t <= num;t++)
34     {
35         scanf("%d%d%d%d",&x,&y,&width_x,&lenth_y);
36         paint(t,x,y,width_x,lenth_y);
37     }
38    
39     scanf("%d%d",&check_x,&check_y);
40     if(ground[check_x][check_y] != 0)
41         printf("%d",ground[check_x][check_y]);
42     else
43         printf("-1\n");
44    
45 
46 
47 //    for(int i = 0;i < MAXSIZE;i++)
48 //    {
49 //        for(int j = 0;j < MAXSIZE;j++)
50 //        {
51 //            printf("%d",ground[i][j]);
52 //        } 
53 //        printf("\n");
54 //    }
55 
56 
57     return 0;
58 }

下面就是

#AC做法#

用到了用两个对角定点代表毯子范围的做法

#include<stdio.h>

/*其他思路:
        针对每一个地毯,给出了其其实坐标,长和宽,就可以确定他的另
        一端点坐标,然后分别储存,逆向判断(从优先级高的也即id号大
        的毯子判断),如果寻找的点横纵坐标在该区域上就输出该id,否
        则往下直到id=0,此时输出-1结束
*/  
struct pos
{
    int lx;
    int ly;
    int rx;
    int ry;
};
      
struct pos place[10005];
int main()
{
    int n,i;
    int wid,len;
    scanf("%d",&n);
    
    for(i = 1;i <= n;i++)
    {
        scanf("%d%d%d%d",&place[i].lx,&place[i].ly,&wid,&len);
        place[i].rx = place[i].lx + wid -1;
        place[i].ry = place[i].ly + len -1;
    }
    
    int find_x,find_y;
    scanf("%d%d",&find_x,&find_y);
    
    for(i = n;i > 0;i--)
    {
        if(find_x <= place[i].rx && find_x >= place[i].lx && find_y <= place[i].ry && find_y >= place[i].ly)
        {
            printf("%d",i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}

#嘻嘻嘻,爱你们哟~~~

 

上一篇:pat 1004 Counting Leaves


下一篇:Pandas进阶之DataFrame多级索引