题目背景
小明骑自行车去上学.....
题目描述
小明去上学的路是一条直线,直线上有 n+1 个关键位置,其中第 i 个关键位置距离家的长度为 si ,其中第一个关键点是家,最后一个关键点是学校。保证 si<si+1 。
小明的自行车是这样一个装置,自行车的向前的加速度最大为 a ,但是刹车装置可以使速度瞬间降至 0 或比当前速度低的任意值。同时,自行车的速度必须时刻保持速度 v≥0。现在他希望尽早的到达学校,不过由于关键点上有红绿灯或是宇宙射线等因素,小明必须在时间段 [li,ri] 中经过第 i 个关键点,现在你需要通过规划自行车的加速和减速,使得小明在满足要求的情况下最早到达学校,如果无论如何都无法到达学校,请输出 "kaibai" (不包含引号)。
绝对误差或相对误差不超过 10−4 即算正确,保证对于无解的数据,即使将任意 li,ri 放大或者缩小 0.001 倍仍然无解。
输入格式
n as1 s2 … sn+1 l1 r1l2 r2…ln+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
数据约束
1≤n≤5000
1≤a≤1000
0=s1<s2<⋯<sn+1≤109
l1=0,r1=109 和 0≤li≤ri≤109
所有输入中的数均为自然数。
部分分
子任务1(30分):保证 n≤10。
子任务2(20分):保证 ri=109
子任务3(30分):保证 n≤300
子任务4(20分):无额外限制。
尾声
感谢闫陈效 (chenxia25) 发现了题面以及数据里的 +∞ 个锅。
感谢程思元 (csy2005) 协助证明题解正确性。