从前,有一个猎人,他对自己的枪法充满信心。 有一天,猎人听到了一个故事,讲的是一位名叫威廉泰尔的瑞士人,他因表演将一个苹果放在儿子的头上,然后从远处用箭射下来而闻名。 猎人听了,心想:“我比他还厉害!”并想出了一个表演,他把一个苹果放在一个移动的人身上,然后射杀它。
猎人在广场 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 ≤ 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