No.1041 直線大学

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 238
作問者 : SuunnSuunn / テスター : trineutrontrineutron
8 ProblemId : 3436 / 出題時の順位表
問題文最終更新日: 2020-01-05 19:00:09

問題文

 高橋くんは直線大学(略称:直大)の学生です。
 
 直線大学の今日の講義では、共線な点(同じ直線上にある点たちのこと)について扱いました。高橋くんは今日の講義が面白いと思ったので、座標平面上に$N$個の点を書いて、ひとつの直線が最大でいくつの点を通るかを調べることにしました。実際に高橋くんが$i$番目に書いた点の座標は$(X_i,Y_i)$です。

 しかし、高橋くんは途中で疲れて寝てしまいました。高橋くんの代わりに、この問題の答えを求めてあげてください。

入力

$N$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_N\ Y_N$

$2\le N\le 100$
$0\le X_i,Y_i\le 100$
$i \neq j $であれば$(X_i,Y_i) \neq (X_j,Y_j)$
入力は全て整数である

出力

高橋くんの書いた点を通る数が最大の直線の、通っている点の数を出力してください。

サンプル

サンプル1
入力
2
1 2
3 4
出力
2

$(1,2) , (3,4)$を通る直線以外に、$2$つの点を通る直線はありません。

サンプル2
入力
4
1 2
2 4
3 7
4 8
出力
3

$(1,2), (2,4), (4,8)$は一直線上にあります。

サンプル3
入力
4
0 0
0 1
1 0
1 1
出力
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。