BYTESB - DRIVE

no tags 

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 :-(
@Troika::Bytes, please verify tests cases.

naraysln: 2012-06-07 13:46:03

I am getting WA even if the error is below 10^-6,
i am printing in decimal format up to 12 decimal points


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