P13322 [GCJ 2012 #1C] Out of Gas

你的汽车没油了，你想尽快回家！幸运的是，你的家在山脚下，而你（和你的车）在山顶。不幸的是，你前面还有一辆车，你无法超过它。幸运的是，你的刹车很好用，而且非常强大。 你从山顶以 $0\,\text{m/s}$ 的速度、在 $0$ 秒时刻出发。重力会以恒定加速度将你的车向山下拉。你可以随时使用刹车来减慢速度，或者临时减小加速度，幅度不限。 如果你以最优方式使用刹车，你最快多久能到家？

输入的第一行为测试用例数 $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$ 米处。

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

**说明** **位置与加速度**：一个以恒定加速度 $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 完成。