AT_abc248_e [ABC248E] 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。

输入输出样例 #1

输入 #1

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

输出 #1

6

输入输出样例 #2

输入 #2

1 1
0 0

输出 #2

Infinity

说明/提示

限制条件

• $1 \leq K \leq N \leq 300$
• $|X_i|, |Y_i| \leq 10^9$
• 若 $i \neq j$，则 $X_i \neq X_j$ 或 $Y_i \neq Y_j$
• 所有输入均为整数

样例解释 1

$x=0$，$y=0$，$y=x\pm 1$，$y=-x\pm 1$ 这 $6$ 条直线满足条件。例如，$x=0$ 经过第 $1$、$3$、$5$ 个点。故输出 $6$。

样例解释 2

经过原点的直线有无数条。因此，输出 Infinity。

由 ChatGPT 4.1 翻译