K-colinear Line

题目描述

给定平面上的 $N$ 个点。 对于每个 $1\leq i\leq N$，第 $i$ 个点的坐标是 $(X_i, Y_i)$。 求平面上经过这 $N$ 个点中至少 $K$ 个点的直线的条数。
如果存在无限多条这样的直线，输出 $Infinity$。

输入格式

输入按以下格式从标准输入给出： $N$ $K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

输出格式

输出平面上经过这 $N$ 个点中至少 $K$ 个点的直线的条数，若存在无限多条这样的直线则输出 $Infinity$。

5 2
0 0
1 0
0 1
-1 0
0 -1

6

1 1
0 0

Infinity

提示

$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$. 输入中的所有数值均为整数。六条直线 $x=0$、$y=0$、$y=x\pm 1$ 和 $y=-x\pm 1$ 满足要求。
例如，$x=0$ 经过第 1、3、5 个点。 因此应输出 $6$。
关于原点有无限多条直线经过。 因此应输出 $Infinity$。

标签: AtCoder|abc248E

来源

AtCoder|abc248E