QOJ.ac

QOJ

実行時間制限: 2.0 s メモリ制限: 2048 MB 満点: 100

#16058. Hill Driving

統計

你正开着车在当地的山丘中行驶,准备回到你居住的小镇。你希望能尽可能快地回去;然而,你注意到油箱里没剩多少汽油了。你已经知道了最省油的路线。这条路线的一部分是下坡,一部分是上坡。不同的路段有不同的长度和坡度。用剩下的一点点燃料,你最快能在多长时间内回到家?

我们将为你的汽车建立一个非常简单的燃料消耗模型。汽车的燃料消耗量(每单位行驶距离)将随着你的行驶速度 $v$ 线性增加。然而,还有一个取决于山丘坡度 $s$ 的偏移量。例如,当沿着某条特定的道路下坡时,你可能可以在不消耗任何燃料的情况下以 $10\text{ km/h}$ 的速度行驶;另一方面,如果你在同一条路上上坡行驶,你消耗燃料的速率将与你在平路上以快 $10\text{ km/h}$ 的速度行驶时相同。更具体地说,汽车的燃料消耗量 $c$(单位:升/千米)由下式给出:

$$c = \max(0, \alpha v + \beta s)$$

其中 $\alpha$ 是平路上的标准燃料消耗率,$v$ 是你的速度(单位:$\text{km/h}$),$s$ 是道路的坡度,$\beta$ 是一个正常数。加速和减速不消耗燃料,且可以瞬间完成。

请注意,你的汽车有一个无法超越的最大(安全)速度。

输入格式

第一行包含一个正整数:测试用例的数量,最多为 $100$。接下来是每个测试用例:

  • 一行包含四个浮点数 $\alpha$ ($0.1 \le \alpha \le 100$)、$\beta$ ($0.1 \le \beta \le 100$)、$v_{\max}$ ($10 \le v_{\max} \le 200$) 和 $f$ ($0 \le f \le 50$):分别表示你汽车的标准(平路)燃料消耗率、坡度系数、汽车的最大速度(单位:$\text{km/h}$)以及你剩余的燃料量(单位:升)。
  • 一行包含一个整数 $r$ ($1 \le r \le 10\,000$):路段的数量。
  • $r$ 行,每行包含两个浮点数 $x_i$ 和 $y_i$ ($1 \le x_i \le 1\,000$, $-1\,000 \le y_i \le 1\,000$):分别表示第 $i$ 个路段的水平距离和高度变化(单位均为米)。每个路段具有恒定的坡度。

输出格式

对于每个测试用例:

  • 输出一行,包含一个浮点数:你到达小镇的最快时间(单位:小时)。保证如果能够到达小镇,所需时间一定小于 $24$ 小时。如果无法到达小镇,则该行必须输出 IMPOSSIBLE

你的输出与标准答案的相对或绝对误差应不超过 $10^{-6}$。

样例

输入样例 1

3
10.0 1.0 150 0.0
1
100.0 -100.0
10.0 100.0 150 1.0
2
100 0
100 100
0.5 0.1 100 10
3
1000 0
100 10
100 -10

输出样例 1

1.414214
IMPOSSIBLE
0.072120

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.