E - Camera Control - カメラ・コントロール
Editorial
/ 
『ACM48』は日本で話題のダンスボーカルグループである。
この冬、ACM48はワールドツアーを行うことになり、 あなたはそのツアーにカメラエンジニアとして参加することになった。
あなたの役割はステージ上に設置されたカメラの制御プログラムを書くというものである。
簡単のためステージは2次元座標上にあるものとする。 カメラは360度自由な向きに回転させることができるが、位置を移動させることはできない。
ステージパフォーマンスの間、ACM48の各メンバーは予め決められた通りに移動し、
割り当てられたパートを歌っていく。 ここで、メンバーが移動するルートは折れ線により与えられるものとする。
あなたの制御するカメラはステージパフォーマンスの間、 一人のメンバーのみに焦点を合わせることができる。
また、カメラから向かって複数のメンバーが同じ方向に位置している場合に限り、
カメラの焦点を合わせるメンバーをそれらのメンバーの中で自由に切り替えることができる。
(カメラから伸ばした半直線上に複数のメンバーがいる場合、カメラから見て奥のメンバーに焦点を合わせておくことができる。)
たとえ歌い終わった歌手に焦点を合わせていた場合でも、カメラからそのメンバーに引いた半直線上に別のメンバーがいない限り、カメラの焦点を他のメンバーに写すことはできない。
あなたの仕事はステージパフォーマンスの段取りが与えられたとき、
歌を歌っているメンバーに焦点を合わせることができる最大の時間を求めるプログラムを書くことである。
問題を解くに当たり以下の条件を満たしていると仮定して良い。
入力形式は以下の通りである。
i
番目のメンバーの情報は以下の形式である。
入力中のすべての値は整数である。 また入力中の全ての座標の絶対値は
10^{3}
以下である。
歌を歌っているメンバーに焦点を合わせることができる最大の時間を出力せよ。 出力には
10^{-6}
以上の絶対または相対誤差を含んではならない。
/ 
Time Limit: 2 sec / Memory Limit: 128 MiB
問題文
- ステージパフォーマンスの開始時点ではカメラの焦点を任意のメンバーに合わせることができる
- 各メンバーの移動ルートはカメラに触れない
- 各メンバーは移動ルートの終点に到達したあと、その位置に留まる
入力
N
c_{x} c_{y}
MEMBER\_INFORMATION\_1
MEMBER\_INFORMATION\_2
...
MEMBER\_INFORMATION\_N
N
(
1 ≤ N ≤ 50
) はメンバーの数を表し、
(c_{x}, c_{y})
はカメラの座標を表す。 続いて
N
人のメンバーの情報が与えられる。
M_{i}
x_{i,1} y_{i,1} t_{i,1}
...
x_{i,M_{i}} y_{i,M{i}} t_{i,M_{i}}
L_{i}
b_{i,1} e_{i,1}
...
b_{i,L_{i}} e_{i,L_{i}}
M_{i}
(1 ≤ M_{i} ≤ 100)
はルート上の頂点の数、
(x_{i,j}, y_{i,j})
は
j
番目の頂点の座標、
t_{i,j}
(0 = t_{i,0} < t_{i,j} < t_{i,j+1} ≤ 10^{3})
は
i
番目のメンバーが
j
番目の頂点に到達する時刻、
L_{i}
(0 ≤ L_{i} ≤ 100)
は
i
番目のメンバーが歌うボーカルパートの数、
b_{i,k}
及び
e_{i,k}
(0 ≤ b_{i,k} < e_{i,k} < b_{i,k+1} < e_{i,k+1}
≤ 10^{3})
は
k
番目のボーカルパートの開始時刻と終了時刻を表す。
出力
部分点
- M_{i} = 1 を満たす入力にのみ正解した場合、部分点として 125 点が与えられます
入力例 1
1 0 0 1 10 10 0 1 0 1
出力例 1
1.00000000000000000000
入力例2
2 0 0 1 10 10 0 1 0 1 1 20 20 0 1 1 2
出力例 2
2.00000000000000000000
入力例 3
2 0 0 1 10 10 0 1 0 1 1 -10 10 0 1 1 2
出力例 3
1.00000000000000000000
入力例 4
2 0 0 2 -5 5 0 5 5 10 1 0 6 2 5 5 0 -5 5 10 1 6 10
出力例 4
9.00000000
入力例 5
1 7 -65 2 -65 10 0 65 1 3 2 0 1 23 24
出力例 5
2.00000000
入力例 6
2 0 0 2 100 10 0 -10 10 10 5 0 1 2 3 4 5 6 7 8 9 2 10 0 0 0 10 10 5 1 2 3 4 5 6 7 8 9 10
出力例 6
5.98862017