直線大学 [yukicoder 1041]

https://yukicoder.me/problems/no/1041

解説

https://yukicoder.me/submissions/475004

考えられる直線は無限にあるのだが、最大個数の点を通すであろう直線に絞って考える。
最大個数の点を通すであろう直線は少なくとも2点は通っている直線であることが言える。
なので、この直線を全探索することにしよう。
点を2つ選ぶ選んで、a,bとする。

あとは、この2点を結んだ時の直線に何個の点が乗っているかの計算であるが、傾きを使用しよう。
直線ab上に点iがあるためには、直線abと直線aiの傾きが同じであればいい。
これを頑張って計算する。
直線abの傾きをdy/dx, 直線aiの傾きをdy2/dx2とする。
差分は普通に計算するとして、dy/dx==dy2/dx2を判定したいが、一般に分数で比較するのは危ない。
なので、両辺に×dx×dx2をして、dy×dx2==dy2×dxとしておいて、この等式を満たすかどうかで判定しよう。
満たすなら個数cntをインクリメントする。

それぞれの直線についてcntを求め最大値を求めると答え。
O(N³)で間に合う。
オーダーでは10⁷くらいが目安であり、今回は10⁶なので、まあ大丈夫。

int N, X[101], Y[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    int ans = 2;
    rep(a, 0, N) rep(b, a + 1, N) {
        int dx = X[a] - X[b];
        int dy = Y[a] - Y[b];

        int cnt = 0;
        rep(i, 0, N) {
            int dx2 = X[a] - X[i];
            int dy2 = Y[a] - Y[i];

            if (dy * dx2 == dy2 * dx) cnt++;
        }
        chmax(ans, cnt);
    }
    cout << ans << endl;
}