题目名称	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楼
《骗分导论》第二章例题…… 啊吧啦吧啦吧 2015-08-03 19:44 2楼
怎么处理“穿过”边界的问题呢？每个正方形的左和上边界上的点属于这个正方形，而右和下边界上的点不属于它，这样在从一个区域走到另一个区域的时候就穿过了一个边界 cstdio 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）。

输出：单行输出一个整数，表示机器人最少需要穿越多少次磁场边缘。

样例：

输入：

输出：