statement.md

点と直線

Problem Statement

平面上に幾つか点(座標は全て整数である)が与えられる。平面上に、最も多くの点を通過するような直線を1本だけ引くとき、通過する点の数を求めよ。

Input

入力は以下の形式で表される。

D
N₁
x₁₁ y₁₁
x₁₂ y₁₂
:
x_1N1 y_1N1
N₂
x₂₁ y₂₁
x₂₂ y₂₂
:
x_2N2 y_2N2
:
N_D
x_D1 y_D1
x_D2 y_D2
:
x_DND y_DND

ここでDはデータセットの個数である。さらに、i番目のデータセットにおいて、N_iは点の個数、x_ijおよびy_ijはj番目の点の座標である。

Constraints

入力は以下の条件をすべて満たす。

• 1 <= D <= 100
• 1 <= i <= D を満たすすべての整数iについて、
  • 2 <= N_i <= 50
  • さらに、1 <= j <= N_i を満たすすべての整数jについて、
    • -100 <= x_ij <= 100
    • -100 <= y_ij <= 100

Output

出力は、各データセットごとに直線が通過する点の個数を1行で出力せよ。

Sample Input

2
5
0 0
-1 -1
1 1
2 2
3 -3
6
5 0
0 -2
0 1
0 7
1 3
2 4

Sample Output

4
3