시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 1 | 0 | 0 | 0.000% |
あるところに銃の腕に自信をもつ猟師がいました. 猟師はある日,「ウィリアムテルというスイス人が,息子の頭にりんごを乗せて遠くから矢で撃ち落とすパフォーマンスで有名になった」というお話を聞きました. それを聞いて"自分のほうがもっと凄い!!"と思った猟師は動いている人の上にりんごを乗せて撃ちぬくパフォーマンスを考えつきました.
猟師は広場に $N$ 人の人を集め,それぞれの人の上にりんごを乗せました. $i$ 番目の人は時刻 $t=0$ のとき,座標 $(x_i, y_i)$ にいます. そこから速度ベクトル $(u_i, v_i)$ にしたがって歩きます. すなわち,時刻 $t ≥ 0$ のとき,$i$ 番目の人は座標 $(x_i + t \times u_i , y_i + t \times v_i)$ にいます. ここで,人々は十分小さいので,同じ座標に複数の人がいたり,同じ座標ですれ違ったりできると仮定します.
猟師は人々を驚嘆させるために,一発の弾丸でできるだけ多くのりんごを撃ち落とすことにしました. 猟師は $t ≥ 0$ であるような任意の時刻に,任意の座標から任意の方向に向けて弾丸を放つことができます. 放たれた弾丸は無限の速さで直線軌道で移動し,りんごに当たった場合貫通して移動します. 弾丸を一発だけ打つとき,最大で何個のりんごを撃ち落とせるか計算してください.
入力は以下の形式で与えられる
$N$
$x_1$ $y_1$ $u_1$ $v_1$
$...$
$x_N$ $y_N$ $u_N$ $v_N$
撃ち落とせるりんごの最大個数を1行に出力せよ.
5 0 0 0 0 1 0 -1 1 -1 0 1 -1 1 1 -1 1 -1 -1 1 -1
5
時刻1に5人がy軸上に並ぶので最大5つのりんごを撃ち落とせる.
5 0 0 0 0 1 0 1 0 -1 0 -1 0 1 1 1 1 -1 -1 -1 -1
3
15 -10 9 2 1 2 10 0 -1 -10 -4 0 -3 -2 8 0 -1 0 -10 -1 -2 -8 5 0 -1 -7 -8 -3 1 10 -6 -2 -3 9 -6 1 0 10 -5 3 1 10 1 0 -3 -4 7 0 -1 10 -9 2 2 2 -5 -1 1 9 -10 3 1
5