题目描述

Your car is out of gas, and you want to get home as quickly as possible! Fortunately, your home is at the bottom of a hill and you (in your car) are at the top of it. Unfortunately, there is a car in front of you, and you can't move past it. Fortunately, your brakes are working and they are very powerful.

You start at the top of the hill with speed $0 \, \text{m/s}$ at time $0$ seconds. Gravity is pulling your car down the hill with a constant acceleration. At any time, you can use your brakes to reduce your speed, or temporarily reduce your acceleration, by any amount.

How quickly can you reach your home if you use your brakes in the best possible way?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains three space-separated numbers: a real-valued number $D$, the distance in meters to your home down the hill; and two integers, $N$ and $A$. The distance $D$ will be given in exactly 6 decimal places.

$N$ lines follow, each of which contains two space-separated, real-valued numbers: a time $t_i$ in seconds, and a position $x_i$ in meters. The $t_i$ and $x_i$ values will be given in exactly 6 decimal places.

One line follows, with $A$ space-separated, real-valued numbers $a_i$, which are accelerations in $\text{m/s}^2$. The accelerations will be given in exactly 2 decimal places.

The other car's position is specified by the $(t_i, x_i)$ pairs. The car's position at time $t_i$ seconds is $x_i$ meters measured from the top of the hill (i.e. your initial position). The car travels at constant speed between time $t_i$ and $t_{i+1}$. The positions and times will both be given in increasing order, with $t_0=0$.

For example, if $t_5=10$, $x_5=20$, $t_6=20$, $x_6=40$, then 10 seconds after the start, the other car is 20 meters down the hill; 15 seconds after the start, the other car is 30 meters down the hill; and 20 seconds after the start, the other car is 40 meters down the hill.

输出格式

For each test case, output one line containing "Case #$c$:", where $c$ is the case number (starting from 1). Then output $A$ lines, the $i^{\text{th}}$ of which contains the minimum number of seconds it takes you to reach your home if your acceleration down the hill due to gravity is $a_i$, and you use your brakes in the best possible way. Answers within an absolute or relative error of $10^{-6}$ of the correct answer will be accepted. There should be no blank lines in the output.

3
1000.000000 2 3
0.000000 20.500000
25.000000 1000.000000
1.00 5.00 9.81
50.000000 2 2
0.000000 0.000000
100000.000000 100.000000
1.00 1.01
10000.000000 3 1
0.000000 0.000000
10000.000000 0.100000
10000.100000 100000.000000
1.00

Case #1:
44.7213595
25.000000
25.0
Case #2:
50000.0
50000.0
Case #3:
10140.974143

提示

Notes

Position and Acceleration: An object with a constant acceleration $a \, \text{m/s}^2$ and starting speed of $v_0 \, \text{m/s}$ will move a distance of $v_0 \cdot t + 0.5 \cdot a \cdot t^2$ after $t$ seconds.

Distance on the slope: All the distances and accelerations are given with respect to the straight line down the hill. They are not, for example, horizontal distances; so if your car is accelerating at $2 \, \text{m/s}^2$ with an initial speed of $0 \, \text{m/s}$, and the other car is stopped at $x=1$, it will take exactly 1 second to reach the other car.

The other car: You may never pass the other car, which means that at no time shall your distance down the hill be greater than that of the other car. It may be equal. The cars should be considered as point masses.

Output values: You can print as many decimal places as you like in the output. We will read and compare your answers with ours, and at that time we will be using $10^{-6}$ as a threshold for inaccuracy. So 25, 25.0 and 25.000000 are the same from our perspective. Trailing zeros after the decimal point does not matter.

Limits

• $1 \leq T \leq 20.$
• $1.0 \leq D \leq 10^4.$
• $1.0 \leq a_i \leq 9.81.$
• $0.0 \leq t_i \leq 10^5.$
• $0.0 \leq x_i \leq 10^5.$
• $t_i < t_{i+1}.$
• $x_i < x_{i+1}.$
• $t_0 = 0$
• $x_{N-1} \geq D.$

Test set 1 (10 Pts, Visible Verdict)

• Time limit: 60 12 seconds.
• $1 \leq N \leq 2.$
• $1 \leq A \leq 10.$

Test set 2 (27 Pts, Hidden Verdict)

• Time limit: 120 24 seconds.
• $1 \leq N \leq 2000.$
• $1 \leq A \leq 250.$