【z01】铺地毯
【问题描述】
为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标
系的第一象限)铺上一些矩形地毯。一共有 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 】
carpet.in carpet.out
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
3
【输入输出样例说明】
如下图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,覆盖点(2 ,
2 )的最上面一张地毯是 3 号地毯。
【输入输出样例2 】
carpet.in carpet.out
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
-1
【输入输出样例说明】
如上图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,点(4,5 )
没有被地毯覆盖,所以输出-1。
【数据范围】
对于30% 的数据,有 n ≤2 ;
对于50% 的数据,0 ≤a, b, g, k≤100;
对于100%的数据,有 0 ≤n ≤10,000 ,0≤a, b, g, k ≤100,000。
【题解】
看到a,b,g,k最后小于等于10W。就知道肯定是不能开二维数组的。
然后看到n比较小。我们可以先把n个地毯的信息存下来。
然后因为只有一个坐标。
所以要维护的点只有一个。
我们就for 1-n。然后看一下这个点是否在该地毯的覆盖范围内。
如果是就更新答案为这个地毯(模拟覆盖的过程);
一开始答案赋值为-1.这样可以不用判断有没有地毯覆盖在这个点上。
【代码】
#include <cstdio> int n,a[10001][4],x0,y0,ans=-1; int main()
{
//freopen("F:\\rush.txt","r",stdin);
scanf("%d",&n);
for (int i = 1;i <= n;i++) //输入n个点的信息
scanf("%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3]);
scanf("%d%d",&x0,&y0);
for (int i = 1;i <= n;i++) //根据输入的点,判断i地毯是否覆盖了这个点。
if ( a[i][0] <= x0 && a[i][1] <=y0 && a[i][0] + a[i][2] >=x0 && a[i][1] + a[i][3] >=y0)
ans = i;
printf("%d",ans);
return 0;
}
最新文章
- Selenium-java-获取当前时间
- sql中文日期格式转换(xxxx年x月x日)
- 4.3.5 使用Http:// (Https://)协议连接到ActiveMQ 2015年9月28日
- jquery时间控件datepicker
- ASP.NET MVC 表单提交List到Controller
- OC语言前期准备
- MVC上传文件示例
- ExtJS笔记2 Class System
- Eclipse下导入外部jar包的3种方式 (zhuan)
- Android打开新的Activity并同时关闭当前Activity
- Codeforces Round #329 (Div. 2) A. 2Char 暴力
- 20 个强大的 Sublime Text 插件
- Struts2实现国际化
- System.InvalidCastException: 无法将类型为“Microsoft.Office.Interop.Word.ApplicationClass”的 COM 对象强制转换为接口类型“Microsoft.Office.Interop.Word._Application”。
- Python之字符串详解1
- 关于react-redux中的connect函数
- Windows Server 2012开启多人远程
- java中的mvc和三层结构究竟是什么关系
- 测试修改hosts文件py小工具
- SQL Server扩展事件的使用ring_buffer target时“丢失”事件的原因分析以及ring_buffer target潜在的问题
热门文章
- document.write的注意点
- 【AtCoder Regular Contest 082 A】Together
- BZOJ——3343: 教主的魔法 || 洛谷—— P2801 教主的魔法
- [Angular &; Web] Retrieve user data from Session
- Android 软键盘弹出,界面整体上移的问题
- JS学习笔记 - 自定义右键菜单、文本框只能输入数字
- [React Intl] Render Content with Placeholders using react-intl FormattedMessage
- C++卷积神经网络实例:tiny_cnn代码具体解释(8)——partial_connected_layer层结构类分析(上)
- ORACLE RMAN备份及还原 RMAN能够进行增量备份:数据库,表空间,数据文件
- stm32的timer