bzoj#P2294. 【POJ Challenge】爬山II

【POJ Challenge】爬山II

题目描述

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

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

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

c=max{0,αv+βs}c=\max\{0,\alpha v+\beta s\}

其中 α\alphaβ\beta 是两个常数,vv 是你的速度(km/hkm/h),ss 是斜率。

加速和减速不花费油,且可以瞬间完成。

你的车有一个安全速度,你永远也不能超越这个速度 vmaxvmax,且在一个斜坡上,你必须以同样的速度行驶,不能变速

输入格式

第一行一个正数 TT 表示测试数据组数,接下来是每个测试数据:

第一行四个浮点数 α,β,vmax,f\alpha,\beta,vmax,f 表示两个常数,最大速度和剩余油量。

第二行一个整数 nn 表示斜坡数量。

接下来 nn 行,每行两个浮点数 x,yx,y,表示由当前位置平移向量 (x,y)(x,y) 可以到达下一个斜坡的拐点。

输出格式

TT 行,每行一个浮点数表示你可以回家的最快时间。

保证如果可以回家,一定在 24h24h 内可以到家。

如果不可能到家,输出 IMPOSSIBLE

输出保留两位小数。

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

数据规模与约定

对于 100%100\% 的数据,1T1001\leq T\leq 1000.1α,β1000.1\leq \alpha,\beta \leq 1000<vmax2000<vmax\leq 2000f500\leq f\leq 501n1041\leq n\leq 10^41x1031\leq x\leq 10^3103y103-10^3\leq y\leq 10^3