bzoj#P2294. 【POJ Challenge】爬山II
【POJ Challenge】爬山II
题目描述
lqp18_31 给了 1tthinking 一个很难的问题。这个问题由 NWERC 2011 某道题改编而来。下面是这个问题:
你在家乡的一个山坡上开车回家。你想尽可能快的回家,但是你的油箱里没有太多油了。回家的路是由一些上坡和下坡组成的。每个坡有不同的斜率和长度。如何可以在油量限制的前提下,最快回家呢?
我们把油量的消耗简化为一个很简单的模型。每小时油量消耗会随着速度 线性递增。但是,油量还和坡的斜率 有关。 举个例子,当走下坡路的时候,你可以以 千米每小时的速度行走而不花费任何的油。然后如果你走上坡路,你就需要耗油了。 更加详细的说, 你的汽车每小时耗油是 。那么
其中 和 是两个常数, 是你的速度(), 是斜率。
加速和减速不花费油,且可以瞬间完成。
你的车有一个安全速度,你永远也不能超越这个速度 ,且在一个斜坡上,你必须以同样的速度行驶,不能变速。
输入格式
第一行一个正数 表示测试数据组数,接下来是每个测试数据:
第一行四个浮点数 表示两个常数,最大速度和剩余油量。
第二行一个整数 表示斜坡数量。
接下来 行,每行两个浮点数 ,表示由当前位置平移向量 可以到达下一个斜坡的拐点。
输出格式
共 行,每行一个浮点数表示你可以回家的最快时间。
保证如果可以回家,一定在 内可以到家。
如果不可能到家,输出 IMPOSSIBLE
。
输出保留两位小数。
3
1.000000 1.000000 1.000000 21.213204
10
1000 1000
1000 -1000
1000 1000
1000 -1000
1000 1000
1000 -1000
1000 1000
1000 -1000
1000 1000
1000 -1000
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
14.14
IMPOSSIBLE
0.01
数据规模与约定
对于 的数据,,,,,,,。