← 返回题目列表

AtCoder · yuha_c83_04

D. 心灵加速器 - 某种心灵物体加速器

中文机器翻译题面 查看原题

問題文

东京西边有一座叫“学园俊”的城市。 有许多学校和研究机构专门培训通灵者。
你是就读于学园都市某所学校的超能力者。你的超能力是给物体施加加速度。
你可以随时随地使用超能力。但是,使用超能力有一些条件。首先,当物体静止时,你可以在任意方向施加加速度。另一方面,当物体运动时,你只能在以下方向之一施加加速度:1) 物体的移动方向 2) 相反方向 3) 与移动方向垂直的方向。
今天的训练项目是沿指定的路线移动物体。为了简单起见,路线由二维平面上的线段和圆弧组成。路线没有分岔,所有线段和圆弧都是平滑连接的(没有锐角)。路线从第一段线段的起点开始,到最后一段线段的终点结束。
在初始状态下,物体被放置在赛道的起点。你需要给物体施加加速度,使其沿赛道移动,将物体运送到赛道的终点,并在该位置使其停止。
在实际训练开始之前,教官指示通过模拟计算物体从起点移动到终点的最短时间。你的工作是,当输入赛道的形状以及物体可以施加的最大加速度时, A_{max} 编写一个程序,求出物体从起点移动到终点所需的最短时间。
物体遵循以下基本物理公式。
当物体沿某个方向运动,并且在前方或后方施加加速度时,以下公式成立。
v = v_{0} + at
s = v_{0}t + \frac{1}{2}at^{2}
在这里, v 、 s 、 v_{0} 、 a 、 t 分别表示速度、从起点的距离、初始速度(在起点的速度)、加速度以及物体的移动时间。此外,从这些公式可以导出以下公式。
v^{2} - v_{0}^{2} = 2as
当物体位于圆弧上,并且圆弧的中心方向施加了加速度时,以下公式成立。
a = \frac{v^{2}}{r}
在这里, v 、 a 、 r 分别表示速度、加速度以及圆弧的半径。请注意,由于超能力的使用条件,在圆弧上无法改变物体的速度。

入力

输入格式如下。
N A_{max}
x_{a,1} y_{a,1} x_{b,1} y_{b,1}
x_{a,2} y_{a,2} x_{b,2} y_{b,2} 
...
x_{a,N} y_{a,N} x_{b,N} y_{b,N} 
输入的第一行是两个正整数, N (0 < N ≤ 40,000) 、 A_{max} (1 ≤ A_{max} ≤ 100) 包括 N 表示线段的数量, A_{max} 表示能够对物体施加的最大加速度。 接下来的 N 行给出了线段的信息。每一行是整数 x_{a,i} 、 y_{a,i} 、 x_{b,i} 、 y_{b,i} (-100 ≤ x_{a,i}, y_{a,i}, x_{b,i}, y_{b,i} ≤ 100) 包括 (x_{a,i}, y_{a,i}) 是 在 i 表示第几条线段的起点, (x_{b,i}, y_{b,i}) 是 在 i 表示第几条线段的终点。 i 表示第几条线段的终点是 i+1 第几号起点,保证可以通过圆弧平滑连接。给定的路线可能会自相交, 但在这些地点不得改变方向。

出力

输出使物体从起点移动到终点所需的最短时间。输出应包括 10^{-6} 不得包含超过的绝对或相对误差。

部分点

  • N = 1 的输入给出正确答案,则部分点为 50 积分
  • 1 ≤ N ≤ 2 的输入给出正确答案,则部分点为 75 积分

入力例 1

2 1
0 0 1 0
1 1 0 1

出力例 1

5.2793638507

入力例21

1 1
0 0 2 0

出力例 2

2.8284271082

入力例 3

3 2
0 0 2 0
1 -1 1 2
0 1 2 1

出力例 3

11.1364603512