bzoj#P2265. Hill Driving

Hill Driving

题目描述

You're driving your car in the local hills and returning to your home town.You'd like to get back as quickly as possible;however,you notice that you don't have much fuel left.You know the most efficient route to take.Some parts of this route go downhill.and some go uphill.The different parts have different lengths and slopes.How quickly can you reach home with the little fuel you have left?

We will assume a very simple model for the fuel consumption of your car.Fuel consumption(per unit distance travelled)will increase linearly with your driving speed vv.However,there is an offset which depends on the slope ss of the hill.For example,when going downhill along a particular road,you might be able to go at 1010 km/h without expending any fuel;on the other hand,,if you were travelling that same road uphill,you would expend fuel at the same rate as if you were driving 1010 km/h faster along a flat road.More specifically,the car's fuel consumption cc in liters per kilometer is given by. where αα is the standard fuel consumption rate on a flat road,vv is your speed in km/h,ss is the slope of the road,and ββ is a positive constant.Acceleration and deceleration do not cost fuel and can be done instantaneously.

Note that your car has a maximum (safe) speed which cannot be exceeded.

$c = max$ ($0$,$α \cdot v + β \cdot s$)

αα 是在平路上的油耗,vv 是速度,ss 是坡度,ββ 是个常数。

加速减速不耗能量。你的车是有极速的。不可超越

输入格式

On the first line a positive integer:the number of test cases,at most 100100.After that per test case:

One line with four floating point numbers αβvmaxα,β,vmax and ff:the standard(flat road) fuel consumption rate of your car,the slope factor,the maximum speed of your car in km/h,and the amount of fuel you have left in liters,respectively.

One line with an integer rr:the number of road segments.

rr lines with two floating point numbers xix_i and yiy_i each:the horizontal distance and height change(both in meters)of the ii-th road segment.Each road segment has constant slope.

第一行给出 αβvmaxα,β,vmax ff 表示的是上式的 αβα,β ,极速和油量。 然后是 rr,表示 rr 段路程。 然后给出 rr 个点,表示水平距离和垂直高度。每个坡斜率相同。

输出格式

Per test case:

One line with a floating point number:the fastest time in hours in which you can reach town.It is guaranteed that if it is possible to reach town at all,it will always be possible in less than 2424 hours.If it is impossible to reach town,the line must contain IMPOSSIBLE instead.

Your output should have a relative or absolute error of at most 10610^{−6}

最快到达终点的时间。达不到就写 IMPOSSIBLE

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.414214
IMPOSSIBLE
0.072120

数据规模与约定

100%100\% 的数据满足:0.1α,β1000.1 \le α,β \le 10010vmax20010 \le vmax \le 2000f500 \le f \le 501r1×1041 \le r \le 1 \times 10^41xi1×1031 \le x_i \le 1 \times 10^31×103yi1×103−1 \times 10^3 \le y_i \le 1 \times 10^3