https://atcoder.jp/contests/abc248/tasks/abc248_e

解説

https://atcoder.jp/contests/abc248/submissions/31046558

幾何問題。
以下解法、非常に面倒なので、別の解法があるかも…

（解法に移る前に）

以下のケースでちょっとはまったので、WAではまってる人はこれを確認してみるといいかも。

Infinityのとき

K=1の場合はどのような場合でも無数に解が存在する。
K=1の時は、Infinityと出して終了しよう。

どういった方針を取るか

今回は点を通る直線を題材とした問題であるが、直線は少なくとも2点があれば作成することができる。
逆に3点あると複数の直線ができてしまったり、色々面倒なので、2点を使った直線から解法が導けないか考えてみる。

ここから思考が飛ぶが、試行錯誤がこの間にあったと考えてほしい…

例えば、任意のa番目の点とb番目の点（a＜b）について直線を列挙していったときに、
同一直線状に3点ある直線は3回現れる。点abcを通っていれば、ab,ac,bcの列挙時に出てくる。
同一直線状に4点ある直線は6回現れる。点abcdを通っていれば、ab,ac,ad,bc,bd,cdの列挙時に出てくる。
つまり、同一直線についてはn点あれば、C(n,2)回現れることになる。（関数Cは二項係数）

よって、
cnt[ (ある直線を表す何らかの情報）] := 任意の2頂点を選んだときにある直線が何通りあるか
というのが計算できれば、その個数から直線に何個点があるかを逆算することができる。

『ある直線を表す何らかの情報』

自分はこれに傾きと切片を使った。
入力値が[-10⁹,10⁹]だったので、doubleは落ちそうな気配があり、有理数でどちらも保持する道を選んだ。
傾きをdx/dy, 切片をbup/bdownという風に有理数で定義して、2つの分数について正規化をすれば、
(dx, dy, bup, bdown)の数の組がとある直線を一意に表してくれるようになる。
以下の関数を作って計算している。

getParameter(a,b) := 2頂点a,bを通る直線を表す(dx, dy, bup, bdown)を返す

具体的には
https://blog.hamayanhamayan.com/entry/2018/09/30/203639
っぽいことをやる。

a = (ya - yb) / (xa - xb)
b = (xa * yb - xb * ya) / (xa - xb)

という感じで分数を作って、ソースコードにあるnormalization関数みたいに有理化する感じである。
(xa - xb)が0になるときが注意で、傾きは分子を1にするが、切片は分子をそのままにしている。
縦の直線なので、傾きと切片を定義はできないのだが、便宜上このようにして直線を同一視させている。

pair<ll, ll> normalization(ll up, ll down, bool slope = true) {
    if (down < 0) {
        up *= -1;
        down *= -1;
    }

    if (down == 0) {
        if (slope) up = 1;
    }
    else {
        ll g = gcd(abs(up), down);
        up /= g;
        down /= g;
    }

    return {up, down};
}

int N, K; ll X[301], Y[301];

tuple<ll, ll, ll, ll> getParameter(int a, int b) {
    ll dx = X[a] - X[b];
    ll dy = Y[a] - Y[b];

    tie(dy, dx) = normalization(dy, dx);

    // ya = dy * xa / dx + b
    // b = (ya * dx - dy * xa) / dx

    ll bup = Y[a] * dx - dy * X[a];
    ll bdown = dx;

    tie(bup, bdown) = normalization(bup, bdown, false);
    return { dy, dx, bup, bdown };
}

void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    if (K == 1) {
        cout << "Infinity" << endl;
        return;
    }

    map<tuple<ll, ll, ll, ll>, int> cnt;

    rep(a, 0, N) rep(b, a + 1, N) cnt[getParameter(a, b)]++;

    map<int, int> rcomb;
    rep(n, K, N + 1) rcomb[n * (n - 1) / 2] = 1;

    int ans = 0;
    fore(p, cnt) ans += rcomb[p.second];
    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

K-colinear Line [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） E]

解説

（解法に移る前に）

Infinityのとき

どういった方針を取るか

『ある直線を表す何らかの情報』