[ABC248] E - K-colinear Line
[Q] https://atcoder.jp/contests/abc248/tasks/abc248_e
y=mx+bしか知らんかった(2WA)
map[{m, b}]で同一判定？ 精度足りるわけないやろ？ と思いつつも、正解率がとても高いから甘えてみたらお叱りを受けた。
1. K=1のとき、絶対Infinity
2. 3点とったときに、それが同一直線上かどうかを判定できる。
https://qiita.com/tydesign/items/ab8a5ae52eb9c50ad26a
3. 全部の3点を確認する時間は、
300C3 = 4,455,100 = 10000 * 445
これは全然間に合う。
4. 3重ループをする。辺ijを確定させたあと、頂点kが辺ijに乗っているか確認。乗ってるなら、頂点数をカウントアップ。
5. 辺ijの頂点数がK以上なら、ansのカウントアップ。
6. もう見た2頂点の組み合わせをマッピングしておけば、重複カウントをふせげる。
実装
ll X[303], Y[303];
int main() {
cincout();
ll N, K;
cin >> N >> K;
if (K == 1) {
cout << "Infinity" << endl;
return 0;
}
rep(i, N) {
cin >> X[i] >> Y[i];
}
// 3点とったときに、同じ直線上かどうか判定。
map<pair<ll, ll>, bool> seen; // もう見たpairをマッピング
ll ans = 0;
rep(i, N) {
for (ll j = i + 1; j < N; ++j) {
// 辺ijが基準
if (seen.count({i, j})) continue;
vector<ll> V; // 同一直線上にある頂点の集まり
V.reserve(N);
V.emplace_back(i);
V.emplace_back(j);
ll x1 = X[j] - X[i];
ll y1 = Y[j] - Y[i];
for (ll k = j + 1; k < N; ++k) {
ll x2 = X[k] - X[i];
ll y2 = Y[k] - Y[i];
if (x1 * y2 == x2 * y1) { // 同一直線上にある
V.emplace_back(k);
}
}
if ((ll)V.size() >= K) ++ans;
// もう見た辺をマッピング
rep(j, (ll)V.size()) {
for (ll k = j + 1; k < (ll)V.size(); ++k) {
seen[{V[j], V[k]}] = true;
}
}
}
}
cout << ans << endl;
}