abc248E K-colinear Line

给定二维平面上的N个不同的点，坐标分别为(X[i],Y[i])，问存在多少条直线穿过至少K个点？
1<=K<=N<=300；|X[i]|,|Y[i]|<=1E9

分析：最多只有300个点，可以枚举所有点对构成的直线，用斜率和截距表示，为了避免精度问题，两者用分数来表示。注意，平行与x轴和y轴的直线要特判处理。

#include <bits/stdc++.h>
using i64 = long long;

const int inf = 2E9;

struct Node {
	i64 x, y, u, v;
	bool operator<(const Node &rhs) const {
		if (x != rhs.x) return x < rhs.x;
		if (y != rhs.y) return y < rhs.y;
		if (u != rhs.u) return u < rhs.u;
		return v < rhs.v;
	}
};

i64 gcd(i64 x, i64 y) {
	return y ? gcd(y, x % y) : x;
}

void solve() {
	i64 N, K;
	std::cin >> N >> K;
	std::vector<i64> X(N), Y(N);
	for (i64 i = 0; i < N; i++) {
		std::cin >> X[i] >> Y[i];
	}

	if (K == 1) {
		std::cout << "Infinity\n";
		return;
	}

	std::map<Node,std::set<i64>> cnt;
	for (i64 i = 0; i < N; i++) {
		for (i64 j = i + 1; j < N; j++) {
			Node t;
			if (X[i] == X[j]) {
				t = {inf, 0, X[i], 0};
			} else if (Y[i] == Y[j]) {
				t = {0, inf, 0, Y[i]};
			} else {
				i64 dx = X[i] - X[j];
				i64 dy = Y[i] - Y[j];
				i64 z1 = gcd(dx, dy);
				dx /= z1;
				dy /= z1;
				i64 du = X[i] * Y[j] - X[j] * Y[i];
				i64 dv = X[i] - X[j];
				i64 z2 = gcd(du, dv);
				du /= z2;
				dv /= z2;
				t = {dx, dy, du, dv};
			}
			cnt[t].insert(i);
			cnt[t].insert(j);
		}
	}
	i64 ans = 0;
	for (auto &pr : cnt) {
		if (pr.second.size() >= K) {
			ans += 1;
		}
	}
	std::cout << ans << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}