Comet OJ

C1560 [WC2007]疯狂赛车

内存限制：256 MB 时间限制：3000 ms

题目描述

布布是一个《泡泡堂》高手，拥有着近乎完美的战绩。他擅长很多地图，例如“小区 10”、“海盗 14”、“大海 02”等等，不过他最喜欢的地图是“赛车”。

在赛车地图中，每个玩家将得到一辆赛车，从起点出发，比赛谁最先到达终点。

在地图中，包括有障碍、加油站、赛车跑道与沙地。障碍不可通过，并且赛车在赛车跑道与沙地上的行进速度是不一样的。

现在我们来考虑一个简化版的赛车游戏。在这个简化版本的赛车游戏中：

  • 比赛在一个无限大的沙地平面上举行。
  • 赛道是一个从原点出发、由 $n$ 条线段首尾相接组成的折线。
  • 出于安全考虑，赛道不会自交（即折线中的任何两条线段，相邻两条线段有且仅有一个公共点，其他任意两条线段均无公共点）。
  • 赛车在赛道上的速度为 $v_a$，在沙地上的速度为 $v_b$，且满足 $v_a \le v_b$。
  • 为了增加比赛的挑战性，在赛道上逆向行驶是允许的。

布布是一个操作非常精确地选手，他总能按照预想的道路行进至终点，但是她不知道哪个才是最快的路线，聪明的你，能帮助他么？

输入格式

第 $1$ 行包含一个整数 $n$，表示赛道一共有 $n$ 段；第 $2$ 行包含两个实数 $v_a$ 与 $v_b$，分别表示赛车在赛道上与沙地中的行进速度。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 与 $y_i$，依次表示赛道的每一个转折点。即赛道的第一个线段是 $(0, 0) \to (x_1, y_1)$，第二条线段是 $(x_1, y_1) \to (x_2, y_2)$，依次类推。其中 $(x_n, y_n)$ 为终点。

输出

仅包含一个实数，表示从起点到终点最少所需时间。精确到小数点后 $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| \le 0.0001 \ 5 & |YourAnswer-OurAnswer| \le 0.01 \ 0 & Otherwise \end{cases}$

【数据规模】

对于 $20\%$ 的数据，赛道的折线段平行于坐标轴。对于 $40\%$ 的数据，$n \le 50$。对于 $100\%$ 的数据，$n \le 1000，1 \le v_b \le v_a \le 20$。所有的坐标都在 $[-10^6, 10^6]$ 内。