QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[+1]

# 5170. 加速度

统计

题目背景

小明骑自行车去上学.....

题目描述

小明去上学的路是一条直线,直线上有 n+1 个关键位置,其中第 i 个关键位置距离家的长度为 si ,其中第一个关键点是家,最后一个关键点是学校。保证 si<si+1

小明的自行车是这样一个装置,自行车的向前的加速度最大为 a ,但是刹车装置可以使速度瞬间降至 0 或比当前速度低的任意值。同时,自行车的速度必须时刻保持速度 v0。现在他希望尽早的到达学校,不过由于关键点上有红绿灯或是宇宙射线等因素,小明必须在时间段 [li,ri] 中经过第 i 个关键点,现在你需要通过规划自行车的加速和减速,使得小明在满足要求的情况下最早到达学校,如果无论如何都无法到达学校,请输出 "kaibai" (不包含引号)。

绝对误差或相对误差不超过 104 即算正确,保证对于无解的数据,即使将任意 li,ri 放大或者缩小 0.001 倍仍然无解。

输入格式

n as1 s2  sn+1                                                                                                                                                                                                                                                                              l1 r1l2 r2ln+1 rn+1

输出格式

一行一个浮点数表示答案,请注意输出的小数点后位数达到了足够的精度。

样例数据

input

4 2 
0 2 8 10 12 
0 1000000000 
2 2 
4 4 
6 7 
6 1000000000

output

6.5857864376

input

5 1 
0 1 2 3 4 5 
0 1000000000 
1 2 
2 3 
3 4 
4 5 
5 6

output

5.0000000000

数据约束

1n5000

1a1000

0=s1<s2<<sn+1109

l1=0,r1=1090liri109

所有输入中的数均为自然数。

部分分

子任务1(30分):保证 n10

子任务2(20分):保证 ri=109

子任务3(30分):保证 n300

子任务4(20分):无额外限制。

尾声

感谢闫陈效 (chenxia25) 发现了题面以及数据里的 +∞ 个锅。

感谢程思元 (csy2005) 协助证明题解正确性。