洛谷P1003 [NOIP 2011 提高组] 铺地毯-题解
题目描述
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 张地毯，编号从 到 。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入格式
输入共 行。
第一行，一个整数 ，表示总共有 张地毯。
接下来的 行中，第 行表示编号 的地毯的信息，包含四个整数 ，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 以及地毯在 轴和 轴方向的长度。
第 行包含两个整数 和 ，表示所求的地面的点的坐标 。
输出格式
输出共 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
| 3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
|
输出 #1
输入输出样例 #2
输入 #2
1
2
3
4
5
| 3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
|
输出 #2
说明/提示
【样例解释 1】
如下图， 号地毯用实线表示， 号地毯用虚线表示， 号用双实线表示，覆盖点 的最上面一张地毯是 号地毯。
【数据范围】
对于 的数据，有 。
对于 的数据， 。
对于 的数据，有 , 。
noip2011 提高组 day1 第 题。
思路
很简单的暴力枚举题。我的思路是先定义地毯的对象，创建一个地毯的vector，把所有地毯的坐标和长宽都存进去；然后倒过来，从最后一张地毯开始往前判断，当前地毯是否包含点坐标，如果包含就记录当前的地毯编号，退出循环。如果遍历完没用找到，输出-1；如果找到了，输出编号。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
class carpet
{
public:
int a, b, g, k;
int id;
carpet() : a(0), b(0), g(0), k(0), id(0) {}
void setCarpet(int a, int b, int g, int k)
{
this->a = a;
this->b = b;
this->g = g;
this->k = k;
}
int IsInside(int x, int y)
{
if (x<a || x>(a + g) || y<b || y>(b + k))
return 0;
else
return 1;
}
};
int main()
{
int n;
scanf("%d", &n);
vector<carpet> c(10000);
for (int i = 0; i < n; i++)
{
c[i].id = i + 1;
int a, b, g, k;
scanf("%d %d %d %d", &a, &b, &g, &k);
c[i].setCarpet(a, b, g, k);
}
int x, y;
scanf("%d %d", &x, &y);
int t = -1;
for (int i = n-1; i >= 0; i--)
{
if (c[i].IsInside(x, y))
{
t = c[i].id;
break;
}
}
printf("%d\n", t);
}
|