P3218 [HNOI2011] 赛车游戏

题目描述

名歌手LAALA最近迷上了一款赛车游戏,游戏中开车的玩家在不同的路段需要选择不同的速度,使得自己在最短的时间内到达终点。开始游戏时,车内的初始油量为f,所以游戏的关键是如何在速度和耗油量之间实现平衡。 LAALA 经过一段时间的研究后,发现这款游戏可以用一个简单的数学模型来描述,具体来说:从起点到终点的路线可以被简化成折线段,每条线段代表一个上坡或者下坡,若在一段斜率为 s(s>0 代表上坡,s=0 代表平地,s

输入格式

从文件input.txt中读入数据,输入文件的第一行是一个正整数T,表示数据组数。对每组数据,第一行是用空格隔开的4个浮点数a、b、vmax和f,其中a、b和vmax的意义如前所述,f表示初始油量,其单位也与前面的描述保持一致。第二行是一个正整数r,表示线段的数目。接下来的r行,每行是用空格隔开的2个浮点数xi和yi,分别表示在标准笛卡耳坐标系下该线段在水平方向和垂直方向的改变量(单位为米)。

输出格式

输出文件 output.txt 包含 T 行,依次对应输入中的 T 组数据。对某组数据,若基于初始油量无法到达终点,则对应行输出 IMPOSSIBLE,否则输出最少需要的时间(单位为小时)。

说明/提示

【数据范围】 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 位,当且仅当你的输出与标准答案完全一致时你的输出才被视作正确。