Description

The map contains obstacles, gas stations, race track, and sand. Obstacles are impassable, and the car’s speed differs between the race track and the sand.

Now we consider a simplified racing game. In this simplified version:

• The race takes place on an infinite sandy plane.
• The track is a polyline starting from the origin, composed of $n$ connected segments.
• For safety, the track does not self-intersect (i.e., in the polyline, adjacent segments share exactly one common point, and any other pair of segments has no common point).
• The car’s speed on the track is $v_a$, and on the sand is $v_b$, with $v_a \geq v_b$.
• To increase the challenge, driving in the reverse direction along the track is allowed.

Bubu is extremely precise and can always follow the intended path to the finish, but he does not know which route is the fastest. Can you help him?

Input Format

The first line of the input file racing.in contains an integer $n$, the number of segments in the track. The second line contains two real numbers $v_a$ and $v_b$, representing the car’s speed on the track and on the sand, respectively.

The next $n$ lines each contain two integers $x_i$ and $y_i$, giving each turning point of the track in order. That is, the first segment of the track is $(0,0)\rightarrow (x_1 , y_1)$, the second segment is $(x_1 , y_1)\rightarrow ( x_2 , y_2)$, and so on. Here $(x_n , y_n)$ is the finish point.

Output Format

The output file racing.out contains a single real number, the minimum time required to go from the start to the finish. Print to 6 decimal places.

2
2 1
0 4
4 4

4.000000

2
2 1
4 4
4 -4

5.464102

Hint

Scoring:

$$YourScore=\begin{cases}10 & |YourAnswer-OurAnswer|\leq 0.0001\\ 5 & |YourAnswer-OurAnswer|\leq 0.01 \\ 0 & Otherwise \end{cases}$$

Constraints:

• For 20% of the testdata, the polyline segments of the track are parallel to the coordinate axes.
• For 40% of the testdata, $n \leq 50$.
• For 100% of the testdata, $n \leq 1000$, $1 \leq v_b \leq v_a \leq 20$.
• All coordinates are within $[-10^6 , 10^6]$.

Translated by ChatGPT 5