BYTESB - DRIVE
Black Widow needs to get to the Avengers’ aid and fast. Stark may have lent her his new Audi but she forgot to fuel it up (people make all kinds of stupid mistakes, but if they look like Scarlet Johansson, who cares?). She needs to cross the next hill to get to her team but there’s only a little fuel left. So, obviously she’ll take the most efficient route. However, some parts of this route go uphill, some go downhill – each part with a different slope and different length.
The fuel expenditure (per unit distance travelled) increases linearly with the driving speed v but there’s also an offset that depends on the slope s of the hill – let’s say when going downhill on a particular road, she might be able to go at 8 km/h without expending any fuel on the other hand, if she were to travel that same road uphill, she would expend fuel at the same rate as if she were driving 8 km/h faster along a flat road.
The car’s fuel consumption c in litres per kilometer is given by
- c = max(0, a*v + b*s)
where
- a: fuel expenditure rate on a flat road,
- v: speed in km/h,
- s: inclination of the road,
- b: positive constant.
Acceleration and deceleration are instantaneous and do not cost any fuel. There is also a safe speed limit that she can’t exceed. How quickly can she get there?
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
One line with four floating point numbers a (0.1 <= a <= 100), b (0.1 <= b <= 100), vmax (10 <= vmax <= 200) and f (0 <= f <= 50): 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 r (1 <= r <= 10000): the number of road segments.
r lines with two floating point numbers xi and yi (1 <= xi <= 1000, -1000 <= y <= 1000) each: the horizontal distance and height change (both in meters) of the i-th road segment. Each road segment has constant slope.
Output
One line per test case: the earliest time in hours in which you can make it to the town. It is guaranteed that if it is possible it will always be possible in <= twenty four hours. If impossible then output “IMPOSSIBLE” instead.
Your output should have a relative or absolute error of at most 10-6.
Sample
Input 2 1.0 100.0 200.0 10 2 1000 0 1000 -1000 10.0 1.0 150 0.0 1 100.0 -100.0 Output 0.1141421356 1.414213562
hide comments
Oleg:
2024-01-10 03:51:21
Strongly suspect issue with tests :-(
|
|
naraysln:
2012-06-07 13:46:03
I am getting WA even if the error is below 10^-6,
|
Added by: | Troika::Bytes |
Date: | 2012-02-16 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |