题目名称 | 316. [AHOI2005] 穿越磁场 |
---|---|
输入输出 | cross.in/out |
难度等级 | ★★☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试数据 | 10 |
题目来源 | BYVoid 于2009-04-17加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:18, 提交:58, 通过率:31.03% | ||||
lrz | 100 | 0.000 s | 0.00 MiB | C++ |
梦恋D | 100 | 0.002 s | 0.29 MiB | C++ |
wrz91win | 100 | 0.002 s | 0.29 MiB | C++ |
Sky_miner | 100 | 0.002 s | 0.47 MiB | C++ |
Furyton | 100 | 0.003 s | 0.31 MiB | C++ |
6434 | 100 | 0.010 s | 0.31 MiB | C++ |
啊吧啦吧啦吧 | 100 | 0.010 s | 0.42 MiB | C++ |
zhengtn03 | 100 | 0.013 s | 0.65 MiB | C++ |
Lethur | 100 | 0.014 s | 5.69 MiB | C++ |
Hzoi_chairman | 100 | 0.015 s | 0.26 MiB | C++ |
关于 穿越磁场 的近10条评论(全部评论) | ||||
---|---|---|---|---|
回复 @峻拔的鸭子 :
大神有木有别的方法,小弟想学学。
NVIDIA
2015-08-04 18:16
3楼
| ||||
《骗分导论》第二章例题……
| ||||
怎么处理“穿过”边界的问题呢?每个正方形的左和上边界上的点属于这个正方形,而右和下边界上的点不属于它,这样在从一个区域走到另一个区域的时候就穿过了一个边界
|
探险机器人在Samuel星球上寻找一块奇特的矿石,然而此时它陷入了一片神秘的磁场区域,动弹不得。
探险空间站立刻扫描了这片区域,绘制出该区域的磁场分布平面图。这片区域中分布了N个磁场,每个磁场呈正方形,且边与坐标轴平行。
例如下图中,存在3个磁场,白点表示机器人的位置,黑点表示矿石的位置:
科学家们分析平面图,进一步发现:这些磁场为大小不一的正方形,可能相交,甚至覆盖,但是它们的边缘不会重合,顶点也不会重合。
例如下面的两种情形是不会出现的:
科学家们给探险机器人启动了磁力罩,这样它就可以在磁场中自由穿越了。
初始时,探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制,在穿越过程中机器人只能够水平或垂直移动,且不能够沿着磁场的边缘行动。
由于磁力罩的能量有限,科学家们希望探险机器人穿越尽量少的磁场边缘采集到这块矿石。例如上图中,探险机器人最少需要穿越两次磁场边缘。
现在小联请你编写程序,帮助科学家们设计探险机器人的路线,统计探险机器人最少需要穿越多少次磁场边缘。
输入:第一行有一个整数N,表示有N个磁场(1 < N < 100)。随后有N行,每行有三个整数X、Y、C(0 < X ,Y ,C < 10000),表示一个磁场左下角坐标为(X,Y),边长为C。接下来有一行,共有四个整数SX, SY, TX, TY,表示机器人初始坐标为(SX, SY),矿石坐标为(TX,TY)(其中,1 < SX, SY, TX, TY < 10000)。
输出:单行输出一个整数,表示机器人最少需要穿越多少次磁场边缘。
样例:
输入:
2 1 3 3 2 1 4 0 0 3 4
输出:
2