P1003 铺地毯 noip2011提高组day1第1题

admin

题目描述

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

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

输入输出格式

输入格式：
输入文件名为carpet.in 。

输入共n+2 行。

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

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

第n+2 行包含两个正整数 x 和y，表示所求的地面的点的坐标（x ，y）。

输出格式：
输出文件名为carpet.out 。

输出共1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1 。

输入输出样例

输入样例#1：
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
输出样例#1：
3

输入样例#2：
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
输出样例#2：
-1
说明

【样例解释1】

如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2,2）的最上面一张地毯是 3 号地毯。



【数据范围】

对于30% 的数据，有 n ≤2 ；

对于50% 的数据，0 ≤a, b, g, k≤100；

对于100%的数据，有 0 ≤n ≤10,000 ，0≤a, b, g, k ≤100,000。

admin

1. #include <iostream>
   
2. using namespace std;
   
3. const int mn=10010;
   
4. int a[mn],b[mn],g[mn],k[mn];
   
5. int x,y,c,n,i;
   
6. bool b1,b2,b3,b4;
   
7. int main()
   
8. {
   
9.     cin>>n;
   
10.     for (i=1; i<=n; i++)
    
11.         cin>>a[i]>>b[i]>>g[i]>>k[i];
    
12.     cin>>x>>y;
    
13.     c=-1;
    
14.     for (i=1; i<=n; i++)
    
15.     {
    
16.         b1=x>=a[i];
    
17.         b2=y>=b[i];
    
18.         b3=x<=a[i]+g[i];
    
19.         b4=y<=b[i]+k[i];
    
20.         if (b1&&b2&&b3&&b4) c=i;
    
21.     }
    
22.     cout<<c;
    
23.     return 0;
    
24. }
    

复制代码

admin

直接模拟即可，注意先要读的数据保存起来，然后在一个个的比较，而每个比较又要分成四个小条件。
还有一个做法就是倒着找，一旦找到就break。

GTR

1. #include<iostream>
   
2. using namespace std;
   
3. int a[10001][5];
   
4. int main()
   
5. {
   
6.     int al,b,n;
   
7.     cin>>n;
   
8.     for(int i=1; i<=n; i++)
   
9.     {
   
10.         cin>>a[i][1]>>a[i][2]>>a[i][3]>>a[i][4];
    
11.         a[i][3]+=a[i][1];
    
12.         a[i][4]+=a[i][2];
    
13.     }
    
14.     cin>>al>>b;
    
15.     for(int i=n; i>=1; i--)
    
16.     {
    
17.         if(a[i][1]<=al&&a[i][2]<=b&&a[i][3]>=al&&a[i][4]>=b)
    
18.         {
    
19.             cout<<i<<endl;
    
20.             return 0;
    
21.         }
    
22.     }
    
23.     cout<<-1<<endl;
    
24.     return 0;
    
25. }
    

复制代码

吴语林

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <algorithm>
   
7. using namespace std;
   
8. int main()
   
9. {
   
10.     int a[12223][10]={0},n,i,d=-1,x,y;
    
11.     scanf("%d",&n);
    
12.     for(i=1;i<=n;i++)
    
13.     {
    
14.             scanf("%d",&a[i][1]);
    
15.             scanf("%d",&a[i][2]);
    
16.             scanf("%d",&a[i][3]);
    
17.             scanf("%d\n",&a[i][4]);
    
18.         }
    
19.         scanf("%d %d",&x,&y);
    
20.         for(i=1;i<=n;i++)
    
21.         {
    
22.                 if(x>=a[i][1]&&x<=a[i][1]+a[i][3]&&y>=a[i][2]&&y<=a[i][2]+a[i][4])
    
23.                 d=i;
    
24.         }
    
25.         printf("%d",d);
    
26. }

复制代码