Apples

Time Limit : 5 sec, Memory Limit : 131072 KB

問題 C : Apples

問題文

あるところに銃の腕に自信をもつ猟師がいました. 猟師はある日,「ウィリアムテルというスイス人が,息子の頭にりんごを乗せて遠くから矢で撃ち落とすパフォーマンスで有名になった」というお話を聞きました. それを聞いて"自分のほうがもっと凄い!!"と思った猟師は動いている人の上にりんごを乗せて撃ちぬくパフォーマンスを考えつきました.

猟師は広場に 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_0 y_0 u_0 v_0
...
x_{N-1} y_{N-1} u_{N-1} v_{N-1}

出力形式

撃ち落とせるりんごの最大個数を1行に出力せよ.

制約

  • 1 ≤ N ≤ 200
  • 0 ≤   |x_i|,   |y_i|   ≤ 10
  • 0 ≤   |u_i|,   |v_i|   ≤ 3
  • 入力値はすべて整数である。

入出力例

入力例 1

5
0 0 0 0
1 0 -1 1
-1 0 1 -1
1 1 -1 1
-1 -1 1 -1

出力例 1

5

時刻1に5人がy軸上に並ぶので最大5つのりんごを撃ち落とせる.

入力例 2

5
0 0 0 0
1 0 1 0
-1 0 -1 0
1 1 1 1
-1 -1 -1 -1

出力例 2

3  

入力例 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

出力例 3

5

Source: ACM-ICPC Japan Alumni Group Summer Camp 2013 , Day 2, Tokyo, Japan, 2013-09-21
http://acm-icpc.aitea.net/
http://jag2013summer-day2.contest.atcoder.jp/