BZPRO

#2931. [Poi1999]溜冰场问题

内存限制：128 MiB 时间限制：1 Sec
提交 提交记录 讨论

题目描述

一场溜冰比赛在Byteland最大的溜冰场举行。溜冰场是一个大小为10000 * 10000的正方形。一个选手在裁判选定的起点开始滑冰，他的任务是滑到由裁判选定的终点。起点和终点不相同。一个选手在滑冰场的平行赛道上滑行。在滑冰场上设置了一些障碍物。每一个障碍物是一个棱柱，它的底部是边与滑冰场的各边平行的多边形。底部的每两个相邻的边总是垂直的。障碍物没有公共点。每一个滑道完结于一个点，在一个选手首先碰到一个障碍物的垂直于滑道方向一面。换一句话说，仅当一个选手撞到墙或者到了终点才能停下来。摔到溜冰场外则取消参赛资格。选手可以沿着障碍物的墙滑行。

判断一个选手依照所给的规则是否可以到达终点，假设他从起点开始滑行。如果如此，那么他需要滑行的最少数目是多少？
任务
写一个程序:
  • 读取溜冰场，障碍物的描述和起点终点的坐标，
  • 检验，一个从起点出发，遵循上述规则滑行的选手是否可以到达终点，如果可以，计算他需要滑行的最少数目，
  • 把结果输出

输入格式

 
我们定义一个坐标系统来描述滑冰场物体的位置。滑冰场是一个顶点分别为(0,0),(10000,0),(10000,10000),(0,10000)的正方形。在输入文件LOD.IN的首行有两个被单空格号隔开的整数z1 和 z2 ，0<=z1, z2<=10000。数字对(z1, z2)表示起点的坐标。在文件的第二行有两个被单空格号分开的整数t1 和t2 （0<=t1, t2<=10000）。数字对（t1, t2）表示终点的坐标。在文件的第三行包含了一个整数s,（1<=s<=2500）。这是障碍物的数目。下面的几行是对障碍物的描述。每一个障碍物的描述由一行包括一个等于障碍物的墙数（底边）的正整数r开始。接下来的r行的每一行有两个由单空格号隔开的整数x和y。那是障碍物底部顶点的坐标，按照顺时针顺序给出。（当按照这个方向绕障碍物一圈，它的内部在左手边）。障碍物的墙的总数不超过10000。

输出格式

  • 如果从起点到终点是不可能的，则字符串为‘NIE’，
  • 如果可能，则写出到达终点的最小滑行数。

样例

样例输入


			
40 10

5 40

3

6

0 15

0 60

20 60

20 55

5 55

5 15

12

30 55

30 60

60 60

60 0

0 0

0 5

55 5

55 35

50 35

50 40

55 40

55 55

6

30 25

15 25

15 30

35 30

35 15

30 15

样例输出


			
 

4

数据范围与提示

BZPRO Powered by Remmina.
Github Repository