专栏首页小樱的经验随笔Vjios P1736 铺地毯【暴力,思维】

Vjios P1736 铺地毯【暴力,思维】

铺地毯

描述

为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有n张地毯,编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

格式

输入格式

输入共n+2行。

第一行,一个整数n(0 <= n <= 10,000),表示总共有n张地毯。

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

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

输出格式

输出共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

限制

1s

来源

NOIp2011提高组Day1第一题

题目链接:https://vijos.org/p/1736

分析:要找铺在最上面的编号,实际上就是for去扫一遍,判断点是否满足条件在区域内的条件,满足就将i的值赋给给ans,否则ans=-1;

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=100010;
 4 int a[N],b[N],g[N],k[N];
 5 int n,x,y,ans=-1;
 6 int main()
 7 {
 8     cin>>n;
 9     for(int i=1;i<=n;i++)
10         cin>>a[i]>>b[i]>>g[i]>>k[i];
11     cin>>x>>y;
12     for(int i=1;i<=n;i++)
13     {
14         if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i])
15             ans=i;
16     }
17     cout<<ans<<endl;
18     return 0;
19 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 回溯算法入门及经典案例剖析(初学者必备宝典)

    前言 基于有需必写的原则,并且当前这个目录下的文章数量为0(都是因为我懒QAQ),作为开局第一篇文章,为初学者的入门文章,自然要把该说明的东西说明清楚,于是。。...

    Angel_Kitty
  • 2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

    Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K...

    Angel_Kitty
  • HDU 2503 a/b + c/d(最大公约数与最小公倍数,板子题)

    话不多说,日常一水题,水水更健康!┗|`O′|┛ 嗷~~ a/b + c/d Time Limit: 1000/1000 MS (Java/Others)   ...

    Angel_Kitty
  • P1003 铺地毯

    题目描述 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 n 张地毯,编号从 1 到n 。现...

    attack
  • 让priority_queue支持小根堆的几种方法

    点击这里了解什么是priority_queue 前言 priority_queue默认是大根堆,也就是大的元素会放在前面 例如 ? #include<io...

    attack
  • 1的个数

    小南刚学了二进制,他想知道一个数的二进制表示中有多少个1,你能帮他写一个程序来完成这个任务吗?

    书童小二
  • 这道算法题太太太太太简单啦

    题目来源于 LeetCode 上第 268 号问题:缺失数字。题目难度为 Easy,目前通过率为 50.2% 。

    五分钟学算法
  • 洛谷2017 5月月赛R1

    我只想说面对这种难度的题目就是冲着20%的数据暴力。。。 分数:40+20+36.1+38+0+19 T1 签到题 III 题目背景 pj组选手zzq近日学会了...

    attack
  • LeetCode--打家劫舍问题

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小...

    宇宙之一粟
  • 训练AI太辛苦?OpenAI新方法:不如让AI之间互教吧

    训练一个AI,往往需要喂大量的正确的合适的样例。 用什么样例合适?判断样例正确的标准是啥?又要多少人力来标注训练的数据? 这些问题想想都头大@_@ 所以呢,Op...

    量子位

扫码关注云+社区

领取腾讯云代金券