JUMP!!! C編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
タロー君たち M 人はハードル走をすることになりました。彼らは xy 座標の x 軸上を x = 0 から x = 10^9 まで、ジャンプで N 個のハードルを跳び越えて走ります。
ハードルの高さ、間隔はバラバラになっており、i 番目のハードルは座標 (d_i, 0) と座標 (d_i, h_i) を結ぶ線分で表されます。(1 ≦ i ≦ N)
i 人目のジャンプの軌道は y = - a_i*(x - B)^2 + c の放物線に従います。
a_i は入力で与えられます。
B は任意の実数、c は 600 です。
ここでは、各走者は点として考え、体の大きさは無視するものとします。
ハードルの置かれ方によって最後まで跳べない可能性があるので何人がたどり着けるかを集計します。
また、今回のハードル走の特別なルールとして、1 回の跳躍で 2 つ以上のハードルを跳び越えてしまう場合は失格となります。ただし、スタート位置から後退して跳躍することはできず、競技中も後退することはできないものとします。
失格せずにすべてのハードルを跳ぶことができる人数を出力してください。
- 入力される値
-
N M
d_1 h_1
d_2 h_2
...
d_N h_N
a_1
a_2
...
a_M
・1 行目には、ハードルの数を表す整数 N と跳ぶ人数を表す整数 M が与えられます。
・i + 1 行目には、i 番目のハードルのスタートからの距離とその高さを表す整数の配列 d_i, h_i が半角スペース区切りで与えられます。同じ d_i は存在しません。ハードルの入力データは原点からの距離順に与えられます。(1 ≦ i ≦ N)
・i + N + 1 行目以降には、i 人目のジャンプ軌道の係数を表す小数の配列 a_i が与えられます。ここで与えられる小数は小数第 3 位まで与えられます。(1 ≦ i ≦ M)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
問題の答えを整数で 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件を満たします。
・1 ≦ N ≦ 100,000 = 10^5
・1 ≦ M ≦ 100,000 = 10^5
・1 ≦ d_i ≦ 1,000,000,000 = 10^9
・d_i < d_{i+1} (1 ≦ i ≦ N)
・1 ≦ h_i ≦ 500
・0.001 ≦ a_i ≦ 500
・ある人が跳べる場合のテストケースでは、全てのハードルの高さに10^-4を足しても結果が変わらないことが保証されます。
・ある人が跳べない場合のテストケースでは、全てのハードルの高さから10^-4を引いても結果が変わらないことが保証されます。
- 入力例1
-
2 5
17 4
49 3
4.059
3.683
3.869
3.110
1.720
- 出力例1
-
5
- 入力例2
-
1 4
2 29
3.194
3.546
4.977
0.018
- 出力例2
-
3
- 入力例3
-
4 3
7 29
15 19
21 1
47 26
0.183
0.209
4.436
- 出力例3
-
0
- 入力例4
-
1 4
44 7
3.458
0.238
4.323
1.817
- 出力例4
-
4
- 入力例5
-
4 4
23 8
36 8
44 8
49 15
2.374
0.177
3.410
4.559
- 出力例5
-
0
