[WC2007] 疯狂赛车
题目背景
布布是一个《泡泡堂》高手,拥有着近乎完美的战绩。他擅长很多地图,例如“小区10”、“海盗14”、“大海02”等等,不过他最喜欢的地图是“赛车”。
在赛车地图中,每个玩家将得到一辆赛车,从起点出发,比赛谁最先到达终点。
题目描述
在地图中,包括有障碍、加油站、赛车跑道与沙地。障碍不可通过,并且赛车在赛车跑道与沙地上的行进速度是不一样的。
现在我们来考虑一个简化版的赛车游戏。在这个简化版本的赛车游戏中:
* 比赛在一个无限大的沙地平面上举行。
* 赛道是一个从原点出发、由$n$条线段首尾相接组成的折线。
* 出于安全考虑,赛道不会自交(即折线中的任何两条线段,相邻两条线段有且仅有一个公共点,其他任意两条线段均无公共点)。
* 赛车在赛道上的速度为$v_a$,在沙地上的速度为$v_b$,且满足 $v_a\geq v_b$。
* 为了增加比赛的挑战性,在赛道上逆向行驶是允许的。
布布是一个操作非常精确的选手,他总能按照预想的道路行进至终点,但是他不知道哪个才是最快的路线,聪明的你,能帮助他么?
输入输出格式
输入格式
输入文件racing.in的第1行包含一个整数$n$,表示赛道一共有$n$段;第2行包含两个实数$v_a$与$v_b$,分别表示赛车在赛道上与沙地中的行进速度。
接下来的$n$行,每行包含两个整数$x_i$与$y_i$,依次表示赛道的每一个转折点。即赛道的第一个线段是$(0,0)\rightarrow (x_1 , y_1)$,第二条线段是$(x_1 , y_1)\rightarrow ( x_2 , y_2)$,依次类推。其中$(x_n , y_n)$为终点。
输出格式
输出文件racing.out仅包含一个实数,表示从起点到终点最少所需时间。精确到小数点后6位。
输入输出样例
输入样例 #1
2
2 1
0 4
4 4
输出样例 #1
4.000000
输入样例 #2
2
2 1
4 4
4 -4
输出样例 #2
5.464102
说明
【评分标准】
每一组数据单独评分,对于每一组数据,你的得分按照如下公式计算:
$$YourScore=\begin{cases}10 & |YourAnswer-OurAnswer|\leq 0.0001\\ 5 & |YourAnswer-OurAnswer|\leq 0.01 \\ 0 & Otherwise \end{cases}$$
【数据规模】
对于20%的数据,赛道的折线段平行于坐标轴。
对于40%的数据,$n\leq 50$ 。
对于100%的数据,$n\leq 1000$ ,$1\leq v_b\leq v_a\leq 20 $。
所有的坐标都在$[-10^6 , 10^6]$内。