网站开发的关键技术有哪些,什么网络营销,wordpress主题恶意代码,目前最流行的拓客方法[NOIP2011 提高组] 铺地毯
https://www.luogu.com.cn/problem/P1003
题目描述
为了准备一个独特的颁奖典礼#xff0c;组织者在会场的一片矩形区域#xff08;可看做是平面直角坐标系的第一象限#xff09;铺上一些矩形地毯。一共有 n n n 张地毯#xff0c;编号从 1 …[NOIP2011 提高组] 铺地毯
https://www.luogu.com.cn/problem/P1003
题目描述
为了准备一个独特的颁奖典礼组织者在会场的一片矩形区域可看做是平面直角坐标系的第一象限铺上一些矩形地毯。一共有 n n n 张地毯编号从 1 1 1 到 n n n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入格式
输入共 n 2 n 2 n2 行。
第一行一个整数 n n n表示总共有 n n n 张地毯。
接下来的 n n n 行中第 i 1 i1 i1 行表示编号 i i i 的地毯的信息包含四个整数 a , b , g , k a ,b ,g ,k a,b,g,k每两个整数之间用一个空格隔开分别表示铺设地毯的左下角的坐标 ( a , b ) (a, b) (a,b) 以及地毯在 x x x 轴和 y y y 轴方向的长度。
第 n 2 n 2 n2 行包含两个整数 x x x 和 y y y表示所求的地面的点的坐标 ( x , y ) (x, y) (x,y)。
输出格式
输出共 1 1 1 行一个整数表示所求的地毯的编号若此处没有被地毯覆盖则输出 -1。
样例 #1
样例输入 #1
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2样例输出 #1
3样例 #2
样例输入 #2
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5样例输出 #2
-1提示
【样例解释 1】
如下图 1 1 1 号地毯用实线表示 2 2 2 号地毯用虚线表示 3 3 3 号用双实线表示覆盖点 ( 2 , 2 ) (2,2) (2,2) 的最上面一张地毯是 3 3 3 号地毯。 【数据范围】
对于 30 % 30\% 30% 的数据有 n ≤ 2 n \le 2 n≤2。 对于 50 % 50\% 50% 的数据 0 ≤ a , b , g , k ≤ 100 0 \le a, b, g, k \le 100 0≤a,b,g,k≤100。 对于 100 % 100\% 100% 的数据有 0 ≤ n ≤ 1 0 4 0 \le n \le 10^4 0≤n≤104, 0 ≤ a , b , g , k ≤ 10 5 0 \le a, b, g, k \le {10}^5 0≤a,b,g,k≤105。
noip2011 提高组 day1 第 1 1 1 题。
由数据可以知道不能直接开二维数组因此我们可以设置四个数组分别记录一下位置以及长度然后我们开始遍历看所要求的点是否被覆盖从前往后进行遍历最后要求的即为最上面的毯子。
代码如下
#includemap
#includeset
#includestack
#includecmath
#includequeue
#includestring
#includebitset
#includecstring
#includeiostream
#includealgorithm
#includenumeric
#define endl \n
using namespace std;typedef long long ll;
typedef pairint, intPII;
const int N3e510;
const int MOD998244353;
const int INF0X3F3F3F3F;
const int dx[]{-1,1,0,0,-1,-1,1,1};
const int dy[]{0,0,-1,1,-1,1,-1,1};
const int M 1e4 10;
int n;
int a[N], b[N], g[N],k[N];
int main()
{cin n;for(int i 1; i n; i ){cin a[i] b[i] g[i] k[i];}int x, y;cin x y;int cnt 0;for(int i 1; i n; i ){if((a[i] x a[i] g[i] x) (b[i] y b[i] k[i] y))cnt i;}if(!cnt) cout -1 endl;else cout cnt endl;return 0;
}
