009 - 直線状の点

問題文

A大学は今年もプログラミングコンテストを開催する。問題作成チームの一員であるあなたは、2次元座標平面上に複数の点を配置した入力データをいくつか生成した。このデータはK個以上の点が同じ直線上にあってはならない。あなたは、作成した入力データがこの条件を満たしているかチェックすることにした。

課題

2次元座標平面上に各点の座標と数Kを入力とし、それらの点の中のK個以上の点が同じ直線上に存在する場合があるか判定するプログラムを作成せよ。

入力・出力

入力

入力は以下の形式で与えられる。

N K
x1 y1
x2 y2
:
xN yN

1行目に座標平面上の点の数N(3≦N≦3000)と整数K(3≦K≦N)が与えられる。続くN行に、点の座標x_i, y_i(0≦x_i, y_i≦10000)が整数で与えられる。ただし、同じ座標をもつ点は与えられない(i ≠ jについて、x_i ≠ x_j または y_i ≠ y_j)。

出力

K個以上の点が同じ直線上に存在すれば「1」、存在しなければ「0」と1行に出力する。

入出力例

入力例 1

5 4
0 0
1 0
1 1
0 1
2 2

出力例 1

0

入力例 2

7 5
0 0
1 0
1 1
0 1
2 0
3 0
4 0

出力例 2

1