幾何の問題． \(O(N^3)\) は間に合うので， 直線すべてを全探探索して，各点に関して直線の上に乗っているかを数えればよい．
実装
\(\,(x_{0}, y_{0}), (x_{1},y_{1})\) を通る直線の式は $$ (y_{0} - y_{1}) x - (x_{0} - x_{1}) y + (y_{1}x_{0} - y_{0}x_{1}) = 0. $$ これを前計算しておけば，直線上に与えられた点が乗っているかは それぞれ \(O(1)\) で求まる．
別解
map: 直線 \(l \mapsto \) \(l\) の上にある点 \(\,(x_{i}, y_{i})\) の個数
を求めておく． 直線 \(l\) の上に \(K\) 個以上点があるのは \(mp[l] \geq {}_{K}C_{2}\) と同値．
注意
- \(N = 1, K = 1\) のときだけ無限に直線の取り方がある．
- 同じ直線を重複して数えない． 直線の式を\(a x + b y + c = 0\) とすれば， \(a,b,c\) が互いに素かつ \(a >= 0\) を仮定すれば， \(a,b,c\) は一意に定まる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, k;
cin >> n >> k;
vll x(n) , y(n);
rep(i,n){
cin >> x[i] >> y[i];
}
if(k == 1){
cout << "Infinity" << endl;
return 0;
}
using T = tuple<ll,ll,ll>;
set<T> v;
rep(i,n) rep(j,i) {
ll a = y[i] - y[j];
ll b = - (x[i] - x[j]);
ll c = - y[i]*x[j] + y[j]*x[i];
ll g = gcd(gcd(a,b),c);
a /= g;
b /= g;
c /= g;
if(a < 0){
a *= -1;
b *= -1;
c *= -1;
}
v.insert({a,b,c});
}
ll ans = 0;
for(auto [a,b,c]: v){
ll cnt = 0;
rep(i,n){
if(a*x[i] + b*y[i] + c == 0) cnt++;
}
if(cnt >= k){
ans++;
}
}
cout << ans << endl;
return 0;
}
