#1965. [HNOI2011]赛车游戏
[HNOI2011]赛车游戏
Background
Special for beginners, ^_^
Description
著名歌手LAALA最近迷上了一款赛车游戏,游戏中开车的玩家在不同的路段需要选择不同的速度,使得自己在最短的时间内到达终点。开始游戏时,车内的初始油量为f,所以游戏的关键是如何在速度和耗油量之间实现平衡。 LAALA 经过一段时间的研究后,发现这款游戏可以用一个简单的数学模型来描述,具体来说:从起点到终点的路线可以被简化成折线段,每条线段代表一个上坡或者下坡,若在一段斜率为s(s>0代表上坡, s=0 代表平地, s<0代表下坡)的道路上以速度vkm/h行驶,则每公里的耗油量为 max (0, av+bs), 其中a和b为游戏的内置参数,分别表示在平地行驶时的耗油率及斜坡对耗油量的影响(b恒为正)。这里假设,加速和减速不耗油,且看成是瞬间完成的,所以即使在同一条线段上也可采取以不同的速度行驶的策略来缩短耗费的时间。 由于 LAALA 在以前的游戏中表现不佳,现在使用的车型依然是系统初始分配的,所以它的速度不能超过 vmax km/h。在获得这些参数后, LAALA 想知道在初始油量受限的情况下(中途不许加油)自己能得到的最佳成绩是多少。作为 LAALA 的歌迷,你能帮帮他吗?
Format
Input
从文件input.txt中读入数据,输入文件的第一行是一个正整数T,表示数据组数。对每组数据,第一行是用空格隔开的4个浮点数a、b、vmax和f,其中a、b和vmax的意义如前所述,f表示初始油量,其单位也与前面的描述保持一致。第二行是一个正整数r,表示线段的数目。接下来的r行,每行是用空格隔开的2个浮点数xi和yi,分别表示在标准笛卡耳坐标系下该线段在水平方向和垂直方向的改变量(单位为米)。
Output
输出文件 output. txt 包含T行,依次对应输入中的T组数据。对某组数据,若基于初始油量无法到达终点,则对应行输出IMPOSS IBLE, 否则输出最少需要的时间(单位为小时)。
Samples
3
10.0 1.0150 0.0
100.0-100.0
10.0100.01501.0
2
1000
100100
0.50.110010
3
10000
1o0I0
100-10
1.41421
IMPOSSIBLE
0.07212
Limitation
【数据范围】 100%的数据满足 T≤100,0.1≤a≤100,0.1≤b≤100,10≤vmax≤200,0≤f≤50,r≤10000,1≤xi≤1000,-1000≤yi≤1000,且如果问题有解,那么答案不超过24。 你所输出的答案需要恰好保留到小数点后5位,当且仅当你的输出与标准答案完全一致时你的输出才被视作正确。