OpenJudge

07:游戏

总时间限制:
1000ms
内存限制:
128000kB
描述

QQDD在玩一个电脑游戏。这个游戏是这样的:

操控一个小人,从(Xa,Ya)点去(Xb,Yb)点。(每个单位长度为1m小人的走路速度为 10km/h

在这个游戏中,有一些高速路,在高速路上小人的速度会加快到 40km/h

每一条高速路有 m 个出入口和m-1 段路组成,其中第i 段路连接第i 个站点和第i+1 个站点。小人必须从一个出入口上高速路,并且沿着高速路走,到某一个出入口离开。

最快到达(Xb,Yb)点的小人的操控者获胜。

DD是游戏王,但 QQ希望打败他,至少不能输给他,所以DD一定要用最少的时间到达。现在 QQ想问问你:在使用最佳策略的情况下,最少需要多少分钟能到达???


输入
第一行四个数 Xa,Ya,Xb,Yb,表示起点和终点的坐标。 接下来每行描述一条高速路,以文件结束符(EOF)结尾。
每行有一些整数,表示这条高速路的站点坐标,每两个数表示一个站点坐标,以(-1,-1)结尾。
输出
一个数,表示最少需要的分钟数,四舍五入取整数。
样例输入
0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1
样例输出
21
提示
站点总数不超过 200
来源
2016HN提高班培训
全局题号
16516
提交次数
0
尝试人数
0
通过人数
0