题目名称 316. [AHOI2005] 穿越磁场
输入输出 cross.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarBYVoid 于2009-04-17加入
开放分组 全部用户
提交状态
分类标签
图论 最短路 离散化
分享题解
通过:18, 提交:58, 通过率:31.03%
Gravatarlrz 100 0.000 s 0.00 MiB C++
Gravatar梦恋D 100 0.002 s 0.29 MiB C++
Gravatarwrz91win 100 0.002 s 0.29 MiB C++
GravatarSky_miner 100 0.002 s 0.47 MiB C++
GravatarFuryton 100 0.003 s 0.31 MiB C++
Gravatar6434 100 0.010 s 0.31 MiB C++
Gravatar啊吧啦吧啦吧 100 0.010 s 0.42 MiB C++
Gravatarzhengtn03 100 0.013 s 0.65 MiB C++
GravatarLethur 100 0.014 s 5.69 MiB C++
GravatarHzoi_chairman 100 0.015 s 0.26 MiB C++
关于 穿越磁场 的近10条评论(全部评论)
回复 @峻拔的鸭子 :
大神有木有别的方法,小弟想学学。
GravatarNVIDIA
2015-08-04 18:16 3楼
《骗分导论》第二章例题……
Gravatar啊吧啦吧啦吧
2015-08-03 19:44 2楼
怎么处理“穿过”边界的问题呢?每个正方形的左和上边界上的点属于这个正方形,而右和下边界上的点不属于它,这样在从一个区域走到另一个区域的时候就穿过了一个边界
Gravatarcstdio
2014-08-27 22:32 1楼

316. [AHOI2005] 穿越磁场

★★☆   输入文件:cross.in   输出文件:cross.out   简单对比
时间限制:1 s   内存限制:128 MiB

探险机器人在Samuel星球上寻找一块奇特的矿石,然而此时它陷入了一片神秘的磁场区域,动弹不得。

探险空间站立刻扫描了这片区域,绘制出该区域的磁场分布平面图。这片区域中分布了N个磁场,每个磁场呈正方形,且边与坐标轴平行。

例如下图中,存在3个磁场,白点表示机器人的位置,黑点表示矿石的位置:

Image:Cross 1.gif

科学家们分析平面图,进一步发现:这些磁场为大小不一的正方形,可能相交,甚至覆盖,但是它们的边缘不会重合,顶点也不会重合。

例如下面的两种情形是不会出现的:

Image:Cross 2.gif

科学家们给探险机器人启动了磁力罩,这样它就可以在磁场中自由穿越了。

初始时,探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制,在穿越过程中机器人只能够水平或垂直移动,且不能够沿着磁场的边缘行动。

由于磁力罩的能量有限,科学家们希望探险机器人穿越尽量少的磁场边缘采集到这块矿石。例如上图中,探险机器人最少需要穿越两次磁场边缘。

现在小联请你编写程序,帮助科学家们设计探险机器人的路线,统计探险机器人最少需要穿越多少次磁场边缘。


输入:第一行有一个整数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