D - Psychic Accelerator - とある超能力の物体加速器
Editorial
/ 
東京の西に『学園都市』と呼ばれる都市がある。
そこには超能力者を育成するための学校や研究所が多数存在している。
あなたは学園都市のとある学校に通う超能力者である。
あなたの超能力は物体に対して加速度を与えるというものである。
あなたはいつでもどこでも超能力を行使することができる。しかし、超能力の行使にはいくつかの条件がある。
まず、物体が静止している場合は、任意の方向に加速度を与えることができる。 一方、物体が動いている場合は、1) 物体の移動方向 2)
その逆方向 3) 移動方向に対して垂直な方向の いずれかにのみ加速度を与えることができる。
今日の訓練メニューは与えられたコースに沿って物体を動かすというものである。
簡単のため、コースは2次元平面上の線分と円弧からなるものとする。 コースに分岐はなく、すべての線分と円弧はなめらかに繋がっているものとする
(鋭いコーナーはないものとする)。 コースは1本目の線分の始点で始まり、最後の線分の終点で終わっている。
初期状態において、物体はコースの始点に置かれている。
あなたは物体に加速度を与え、コースに沿って物体を動かし、コースの終点まで運び、 その位置で停止させなければならない。
実際の訓練に入る前に、教官が物体を始点から終点に動かすまでの最短時間を シミュレートションにより計算するように指示をしてきた。
あなたの仕事は、入力としてコースの形状と物体に与えられることができる最大加速度
A_{max}
が与えられたとき、 物体を始点から終点まで動かすために必要な最短時間を求めるプログラムを書くことである。
物体は以下の基本的な物理公式に従う。
物体がある方向に動いていており、 前方または後方に加速度が働いている場合、 以下の公式が成り立つ。
物体が円弧上にあり、円弧の中心方向に加速度が与えられている場合、 以下の公式が成り立つ。
入力形式は以下の通りである。
物体を始点から終点まで動かすために必要な最短時間を出力せよ。 出力には
10^{-6}
以上の絶対または相対誤差を含んではならない。
/ 
Time Limit: 2 sec / Memory Limit: 128 MB
問題文
v = v_{0} + at
s = v_{0}t + \frac{1}{2}at^{2}
ここで、
v
、
s
、
v_{0}
、
a
、
t
はそれぞれ、 速度、始点からの距離、初期速度(始点での速度)、 加速度および物体の移動時間を表す。 また、これらの式から以下の式が導かれる。
s = v_{0}t + \frac{1}{2}at^{2}
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}
入力の1行目は二つの正の整数、
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
番目の始点に、 円弧によって滑らかにつながることが保証されている。 与えられたコースは自己交差する場合があるが、
それらの地点で向きを変えてはならない。
出力
部分点
- 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