#1721. 【POJ Challenge】爬山II

【POJ Challenge】爬山II

Background

Special for beginners, ^_^

Description

lqp18_31给了1tthinking一个很难的问题。这个问题由NWERC 2011某道题改编而来。下面是这个问题:

你在家乡的一个山坡上开车回家。你想尽可能快的回家,但是你的油箱里没有太多油了。回家的路是由一些上坡和下坡组成的。每个坡有不同的斜率和长度。如何可以在油量限制的前提下,最快回家呢?

我们把油量的消耗简化为一个很简单的模型。每小时油量消耗会随着速度 v 线性递增。但是,油量还和坡的斜率 s 有关。 举个例子,当走下坡路的时候,你可以以10千米每小时的速度行走而不花费任何的油。然后如果你走上坡路,你就需要耗油了。 更加详细的说, 你的汽车每小时耗油是 c 。那么

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

其中 αβ 是两个常数, v 是你的速度 km/h, s 是斜率。 加速和减速不花费油,且可以瞬间完成。你的车有一个安全速度,你永远也不能超越这个速度vmax 且在一个斜坡上,你必须以同样的速度行驶,不能变速 .

Format

Input

第一行一个正数:测试数据组数,最多100。接下来是每个测试数据:

  • 一行是4个浮点数 α (0.1 ≤ α ≤ 100), β (0.1 ≤ β ≤ 100), vmax (0 < vmax ≤ 200) and f (0 ≤ f ≤= 50): 常数αβ ,最大速度和剩余油量。
  • 下一行一个整数 r (1 ≤ r ≤ 10,000): 斜坡数。
  • 接下来 r 行,每行两个浮点数,x~i~ and y~i~ (1 ≤ x~i~ ≤ 1000, -1000 ≤ y~i~ ≤ 1000,单位是米) ,表示由现在的位置平移向量( x~i~ , y~i~ )可以到达下一个斜坡的拐点(斜坡的斜率是不变的)。

Output

每组测试数据:一行一个浮点数:你可以回家的最快时间。保证如果可以回家,一定在24h内可以到家。如果不可能到家,输出"IMPOSSIBLE"。输出保留两位小数

Samples

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

Limitation

1s, 1024KiB for each test case.