一条直线如果覆盖至少 k 个点,就计入答案。
注意:若 k=1,任意经过某个目的地的直线都合法,因此答案是无限条。代码中输出 Infinity。如果评测保证输出为整数,通常不会出现 k=1。
对于 k≥2,任意一条合法直线一定可以由其中任意两个点唯一确定。
因此可以枚举所有点对 (i,j),得到一条直线,再统计所有点中有多少点在这条直线上。如果数量不少于 k,就把这条直线加入集合去重。
小 C 是一名航空调度员,负责一片矩形空域。空域中有 n 个目的地,第 i 个目的地的坐标为 (xi,yi),所有目的地位置两两不同。如果一条笔直的航线经过至少 k 个目的地,小 C 就称这条航线为黄金航线。现在他想知道,整片空域中一共有多少条不同的黄金航线。
特别地,当 k=1 时,过任意一个目的地都可以作出无穷多条直线,此时答案视为无限大,需要输出 Infinity。
目的地的数量 n 不超过 300,1≤k≤n。所有坐标均为整数,且满足 0≤xi,yi≤300。
第一行包含两个整数 n 和 k,以一个空格分隔。 接下来 n 行,每行包含两个整数 xi 和 yi,表示一个目的地的坐标。
输出一个整数,表示黄金航线的条数。如果 k=1,则输出 Infinity。
输入
3 2
0 0
1 1
2 0
输出
3
说明
三个目的地坐标分别为 (0,0)、(1,1)、(2,0),构成一个三角形。当 k=2 时,任意两个点确定一条直线。共存在 3 条不同的直线,每条直线恰好经过 2 个目的地,均满足黄金航线条件,因此输出 3。
输入
4 3
0 0
1 0
2 0
0 1
输出
1
说明
四个点中,(0,0)、(1,0)、(2,0) 三点共线,位于 y=0 这条直线上;点 (0,1) 不在该直线上。当 k=3 时,只有这一条经过 3 个点的直线满足黄金航线条件。其余任意两点确定的直线仅经过 2 个点,不满足 k=3 的要求,因此答案为 1。
输入
3 1
0 0
1 1
2 0
输出
Infinity
说明
当 k=1 时,过任意一个点都可以作出无穷多条直线,因此答案为无限大,按照题目要求输出 Infinity。
输入
5 5
0 0
1 0
2 0
3 0
4 0
输出
1
说明
所有 5 个目的地全部位于 y=0 这条直线上。当 k=5 时,仅这一条直线经过 5 个点,满足黄金航线条件,因此答案为 1。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.