Points on a Straight Line

Time Limit : 3 sec, Memory Limit : 262144 KB

直線上の点

 

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

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

入力

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

$N$ $K$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_N$ $y_N$

1行目に座標平面上の点の数$N$ ($3 \leq N \leq 3000$)と整数$K$ ($3 \leq K \leq N$)が与えられる。続く$N$行に、点の座標$x_i,y_i$ ($0 \leq x_i,y_i \leq 10000$)が整数で与えられる。ただし、同じ座標をもつ点は与えられない($i≠j$について、$x_i\ne x_j $または$y_i \ne 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