/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
座標平面上の N 個の点が与えられます。 1\leq i\leq N について、i 番目の点の座標は (X_i, Y_i) です。
座標平面上の直線であって、N 個の点のうち K 個以上の点を通るものの個数を求めてください。
ただし、そのようなものが無数に存在する場合は Infinity を出力してください。
制約
- 1 \leq K \leq N \leq 300
- \lvert X_i \rvert, \lvert Y_i \rvert \leq 10^9
- i\neq j ならば X_i\neq X_j または Y_i\neq Y_j
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
与えられた N 個の点のうち K 個以上の点を通る直線の数を出力せよ。ただし、そのようなものが無数に存在する場合は Infinity を出力せよ。
入力例 1
5 2 0 0 1 0 0 1 -1 0 0 -1
出力例 1
6
x=0, y=0, y=x\pm 1, y=-x\pm 1 の 6 本の直線が条件をみたします。
例えば、x=0 は、1, 3, 5 番目の 3 個の点を通ります。
よって、6 を出力します。
入力例 2
1 1 0 0
出力例 2
Infinity
原点を通る直線は無数に存在します。
よって、Infinity を出力します。
Score : 500 points
Problem Statement
You are given N points in the coordinate plane. For each 1\leq i\leq N, the i-th point is at the coordinates (X_i, Y_i).
Find the number of lines in the plane that pass K or more of the N points.
If there are infinitely many such lines, print Infinity.
Constraints
- 1 \leq K \leq N \leq 300
- \lvert X_i \rvert, \lvert Y_i \rvert \leq 10^9
- X_i\neq X_j or Y_i\neq Y_j, if i\neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the number of lines in the plane that pass K or more of the N points, or Infinity if there are infinitely many such lines.
Sample Input 1
5 2 0 0 1 0 0 1 -1 0 0 -1
Sample Output 1
6
The six lines x=0, y=0, y=x\pm 1, and y=-x\pm 1 satisfy the requirement.
For example, x=0 passes the first, third, and fifth points.
Thus, 6 should be printed.
Sample Input 2
1 1 0 0
Sample Output 2
Infinity
Infinitely many lines pass the origin.
Thus, Infinity should be printed.