P3218 [HNOI2011]赛车游戏

    • 48通过
    • 126提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 2011 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    名歌手LAALA最近迷上了一款赛车游戏,游戏中开车的玩家在不同的路段需要选择不同的速度,使得自己在最短的时间内到达终点。开始游戏时,车内的初始油量为f,所以游戏的关键是如何在速度和耗油量之间实现平衡。

    LAALA 经过一段时间的研究后,发现这款游戏可以用一个简单的数学模型来描述,具体来说:从起点到终点的路线可以被简化成折线段,每条线段代表一个上坡或者下坡,若在一段斜率为 s(s>0 代表上坡,s=0 代表平地,s<0 代表下坡)的道路上以速度 v km/h 行驶,则每公里的耗油量为 max(0,av+bs),其中 a 和 b 为游戏的内置参数,分别表示在平地行驶时的耗油率及斜坡对耗油量的影响(b 恒为正)。这里假设,加速和减速不耗油,且看成是瞬间完成的,所以即使在同一条线段上也可采取以不同的速度行驶的策略来缩短耗费的时间。

    由于 LAALA 在以前的游戏中表现不佳,现在使用的车型依然是系统初始分配的,所以它的速度不能超过 vmax km/h。在获得这些参数后,LAALA 想知道在初始油量受限的情况下(中途不许加油)自己能得到的最佳成绩是多少。作为 LAALA 的歌迷,你能帮帮他吗?

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#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
    输出样例#1: 复制
    1.41421
    IMPOSSIBLE
    0.07212

    说明

    【数据范围】

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。