布布是一个《泡泡堂》高手,拥有着近乎完美的战绩。他擅长很多地图,例如“小区10”、“海盗14”、“大海02”等等,不过他最喜欢的地图是“赛车”。
在赛车地图中,每个玩家将得到一辆赛车,从起点出发,比赛谁最先到达终点。
在地图中,包括有障碍、加油站、赛车跑道与沙地。障碍不可通过,并且赛车在赛车跑道与沙地上的行进速度是不一样的。
现在我们来考虑一个简化版的赛车游戏。在这个简化版本的赛车游戏中:
比赛在一个无限大的沙地平面上举行。
赛道是一个从原点出发、由n条线段首尾相接组成的折线。
出于安全考虑,赛道不会自交(即折线中的任何两条线段,相邻两条线段有且仅有一个公共点,其他任意两条线段均无公共点)。
赛车在赛道上的速度为va,在沙地上的速度为vb,且满足 。
为了增加比赛的挑战性,在赛道上逆向行驶是允许的。
布布是一个操作非常精确的选手,他总能按照预想的道路行进至终点,但是他不知道哪个才是最快的路线,聪明的你,能帮助他么?