ABC248E - K-colinear Line

考え方

$K=1$ならInfinityなので，その他の場合を考える．

2点を決めれば傾きが決まる．このとき，何点通るかをカウントする．「$x$個の点が一直線上に乗っているとき，この直線はxx回カウントされる」という考え方ができる．
※これに気付かずに，setをつかって区別してしまった．．．
Editorial - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）

傾きが同じかどうかは，

\begin{aligned}
&\frac{\Delta Y_{1}}{\Delta X_{1}}
=\frac{\Delta Y_{2}}{\Delta X_{2}} \\
&\Leftrightarrow
\Delta X_{1}\Delta Y_{2} = \Delta Y_{1} \Delta X_{2}
\end{aligned}

で考えると，整数のまま扱える．

回答例

setを使った回答．

N, K = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(N)]

if K == 1:
    exit(print('Infinity'))

ans = 0
seen = set()
for i in range(N):
    for j in range(i + 1, N):
        cnt = 0
        points = []
        x1 = P[j][0] - P[i][0]
        y1 = P[j][1] - P[i][1]
        for k in range(N):
            x2 = P[k][0] - P[i][0]
            y2 = P[k][1] - P[i][1]
            if x1 * y2 == y1 * x2:
                points.append(k)
                cnt += 1
        points = tuple(sorted(points))
        if cnt >= K and not points in seen:
            ans += 1
            seen.add(points)
print(ans)

このように$i < j$の組み合わせで考えると，$x$個の点を通る直線はちょうど

\begin{aligned}
\binom{x}{2}
=\frac{x (x -1)}{2}
\end{aligned}

回カウントされるから，setなしでも実装できる：

N, K = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(N)]

if K == 1:
    exit(print('Infinity'))

cnt = [0] * (N + 1)
for i in range(N):
    for j in range(i + 1, N):
        tmp = 0
        x1 = P[j][0] - P[i][0]
        y1 = P[j][1] - P[i][1]
        for k in range(N):
            x2 = P[k][0] - P[i][0]
            y2 = P[k][1] - P[i][1]
            if x1 * y2 == y1 * x2:
                tmp += 1
        cnt[tmp] += 1

print(sum(2 * cnt[i] // (i * (i - 1)) for i in range(K, N + 1)))