【bzoj3695】【FJ2014集训】滑行

2014年9月4日1,4120

Description

    首长NOI惨跪,于是去念文化课了。现在,他面对一道物理题。
现在有一个小滑块可以在地面上滑行,地面上被划分成不同的区域,使得小滑块在不同的
区域内部有一个不同的速度上限。
小滑块在(0,0)点,我们现在要推动小滑块到目标点(x,y)。
地面上有N层区域,每层区域都是矩形,现在给你一个序列{Hi}表示每层区域的高度,覆盖的地面横坐标范围是0~X,第i个区域的限速是vi。
注: Y=Sigma(Hi) 其中i从1到N
其它的地方小滑块不允许进入。
现在我们要设计一个路线使得小滑块滑到目标点的用时最小。

Input

  第一行两个整数,分别表示N、x。
第二行N个整数,第i个数表示Hi。。
第三行N个整数,第i个数表示Vi。

Output

  一行一个整数,表示最小用时,保留到小数点后第三位。

Sample Input

1 5
5
1

Sample Output

7.071

HINT

N<=100,X<=1000,对于任意i,满足1<=i<=N-1,有Vi<V(i+1)

题解

根据费马光程原理,此题时间最短路径必定是一条光路。

二分。。。