ユニークビジョンプログラミングコンテスト2022 (AtCoder Beginner Contest 248) E - K-colinear Line (500)
線を傾きとy切片で管理する
傾きはdx,dyで持って$ dx \ge 0とする
どっちかが0で片方が0でないならそれを1に揃えておく
$ \gcd(dx,dy)で両方を割っておく
全2点間で以下を行う
dx,dyを計算
上の変換を行う
既に登場した線の場合は飛ばす
$ dx = 0の場合
y座標だけ違うということ
x座標が同じ点がk個以上あればOK
$ dy = 0の場合
x座標だけ違うということ
y座標が同じ点がk個以上あればOK
それ以外
それぞれの点$ iについて$ dx x_i - dy y_iを計算して、これが今見ている2点のどちらかので計算した値と一致したのがk個以上あればOK
元の切片より$ dx倍しているのは小数を出したくないため
全2点間で全ての点での値を計算するので$ \mathcal{O}(N^3)