Description

你的汽车没油了，你想尽快回家！幸运的是，你的家在山脚下，而你（和你的车）在山顶。不幸的是，你前面还有一辆车，你无法超过它。幸运的是，你的刹车很好用，而且非常强大。

你从山顶以 $0\,\text{m/s}$ 的速度、在 $0$ 秒时刻出发。重力会以恒定加速度将你的车向山下拉。你可以随时使用刹车来减慢速度，或者临时减小加速度，幅度不限。

如果你以最优方式使用刹车，你最快多久能到家？

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行包含三个用空格分隔的数：一个实数 $D$，表示你到家的距离（米）；两个整数 $N$ 和 $A$。$D$ 保证有且仅有 $6$ 位小数。

接下来 $N$ 行，每行包含两个用空格分隔的实数：第 $i$ 个为时间 $t_i$（秒），第 $i$ 个为位置 $x_i$（米）。$t_i$ 和 $x_i$ 都保证有且仅有 $6$ 位小数。

再接下来一行，包含 $A$ 个用空格分隔的实数 $a_i$，表示加速度（$\text{m/s}^2$），每个加速度保证有且仅有 $2$ 位小数。

前车的位置由 $(t_i, x_i)$ 对给出。前车在 $t_i$ 秒时位于山顶下方 $x_i$ 米处（即你的起点）。前车在 $t_i$ 到 $t_{i+1}$ 之间以恒定速度行驶。所有 $t_i$ 和 $x_i$ 均严格递增，$t_0 = 0$。

例如，如果 $t_5=10$，$x_5=20$，$t_6=20$，$x_6=40$，那么开始后 $10$ 秒前车在 $20$ 米处，$15$ 秒时在 $30$ 米处，$20$ 秒时在 $40$ 米处。

Output Format

对于每个测试用例，输出一行 "Case #$c$:"，其中 $c$ 为测试用例编号（从 $1$ 开始）。然后输出 $A$ 行，第 $i$ 行为你在重力加速度为 $a_i$ 时，且以最优方式使用刹车，最快到家的秒数。答案的绝对或相对误差不超过 $10^{-6}$ 即视为正确。输出中不应有空行。

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

Hint

说明

位置与加速度：一个以恒定加速度 $a\,\text{m/s}^2$、初速度 $v_0\,\text{m/s}$ 的物体，在 $t$ 秒后将移动 $v_0 \cdot t + 0.5 \cdot a \cdot t^2$ 米。

坡面距离：所有距离和加速度均以山坡直线方向为准，不是水平距离。例如，你以 $2\,\text{m/s}^2$ 的加速度、初速度 $0\,\text{m/s}$，前车静止在 $x=1$，那么你正好 $1$ 秒能追到前车。

前车：你永远不能超过前车，也就是说，任何时刻你的下坡距离都不能大于前车，可以相等。两车都视为质点。

输出数值：你可以输出任意多的小数位。我们会用 $10^{-6}$ 作为误差阈值进行比较。因此 $25$、$25.0$、$25.000000$ 都被视为相同。小数点后的尾随 $0$ 不影响判分。

限制条件

• $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$

测试集 1（10 分，结果可见）

• 时间限制：60 12 秒
• $1 \leq N \leq 2$
• $1 \leq A \leq 10$

测试集 2（27 分，结果隐藏）

• 时间限制：120 24 秒
• $1 \leq N \leq 2000$
• $1 \leq A \leq 250$

翻译由 ChatGPT-4.1 完成。