QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

#16344. Racing Game

Statistics

The famous singer LAALA has recently become obsessed with a racing game. In the game, players must choose different speeds on different road segments to reach the finish line in the shortest possible time. At the start of the game, the car has an initial fuel amount of $f$, so the key to the game is how to achieve a balance between speed and fuel consumption.

After some research, LAALA discovered that this game can be described by a simple mathematical model. Specifically, the route from the start to the finish can be simplified into a series of line segments, where each segment represents an uphill or downhill slope. If driving at a speed of $v$ km/h on a road segment with a slope $s$ ($s > 0$ represents uphill, $s = 0$ represents flat ground, $s < 0$ represents downhill), the fuel consumption per kilometer is $\max(0, av + bs)$, where $a$ and $b$ are the game's built-in parameters, representing the fuel consumption rate on flat ground and the influence of the slope on fuel consumption, respectively ($b$ is always positive). It is assumed here that acceleration and deceleration consume no fuel and are instantaneous, so even on the same segment, one can adopt a strategy of driving at different speeds to reduce the time taken.

Because LAALA did not perform well in previous games, the car model currently in use is still the one initially assigned by the system, so its speed cannot exceed $v_{max}$ km/h. After obtaining these parameters, LAALA wants to know the best time he can achieve given the limited initial fuel (refueling is not allowed during the journey). As a fan of LAALA, can you help him?

Input

The first line of the input contains a positive integer $T$, representing the number of data sets. For each data set, the first line contains 4 floating-point numbers $a$, $b$, $v_{max}$, and $f$ separated by spaces, where $a$, $b$, and $v_{max}$ have the meanings described above, and $f$ represents the initial fuel amount, with units consistent with the previous description. The second line is a positive integer $r$, representing the number of segments. The following $r$ lines each contain 2 floating-point numbers $x_i$ and $y_i$, representing the change in the horizontal and vertical directions of the segment in the standard Cartesian coordinate system (in meters).

Output

The output contains $T$ lines, corresponding to the $T$ data sets in the input. For a given data set, if it is impossible to reach the finish line based on the initial fuel, output IMPOSSIBLE. Otherwise, output the minimum time required (in hours).

Constraints

$100\%$ of the data satisfies $T \le 100$, $0.1 \le a \le 100$, $0.1 \le b \le 100$, $10 \le v_{max} \le 200$, $0 \le f \le 50$, $r \le 10000$, $1 \le x_i \le 1000$, $-1000 \le y_i \le 1000$. If the problem has a solution, the answer will not exceed $24$.

Your output must be rounded to exactly 5 decimal places. Your output is considered correct if and only if it matches the standard answer exactly.

Examples

Input 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

Output 1

1.41421
IMPOSSIBLE
0.07212

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.