← 返回题目列表

Codeforces · 388/E

E. 狐狸与流星雨

中文机器翻译题面 查看原题

天上有流星雨,有n颗流星。天空可以被视为二维欧几里得平面,流星位于该平面上。

福克斯夏尔看着天空。她发现每颗流星的轨道都是一条直线,并且每颗流星的速度都是恒定的。现在夏尔想知道:任意一对流星在特定时间在同一位置相遇的最大数量是多少?请注意,时间不受限制,也可以为负值。当流星同时出现在同一位置时,它们永远不会相撞。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1000)。接下来的 n 行每行包含 6 个整数: t1, x1, y1, t2, x2, y2 — 流星轨道的描述:在时间 t1,当前流星位于点 (x1, y1),在时间 t2,流星位于点 (x2, y2) ( - 106 ≤ t1, x1, y1, t2, x2, y2 ≤ 106; t1 ≠ t2)。

不会有两颗流星在任何时间总是处于同一位置。

输出

打印一个整数 - 任何一对流星在特定时间在同一位置相遇的最大数量。

示例

输入 #1

2
0 0 1 1 0 2
0 1 0 1 2 0

输出 #1

2

输入 #2

3
-1 -1 0 3 3 0
0 2 -1 -1 3 -2
-2 0 -1 6 0 3

输出 #2

3

输入 #3

4
0 0 0 1 0 1
0 0 1 1 1 1
0 1 1 1 1 0
0 1 0 1 0 0

输出 #3

1

输入#4

1
0 0 0 1 0 0

输出#4

1

注意

在示例 1 中,流星 1 和流星 2 在 t=-1 的 (0, 0) 处相遇。

在示例 2 中,流星 1 和 2 在 t=1 的 (1, 0) 处相遇,流星 1 和 3 在 t=0 的 (0, 0) 处相遇,流星 2 和 3 在 t=2 的 (0, 1) 处相遇。

在示例3中,没有两颗流星相遇。

在示例 4 中,只有 1 颗流星,其速度为零。

如果您的浏览器不支持动画 png,请在此处查看 gif 版本:

http://assets.codeforces.com/images/388e/example1.gif

http://assets.codeforces.com/images/388e/example2.gif

http://assets.codeforces.com/images/388e/example3.gif

http://assets.codeforces.com/images/388e/example4.gif