で図形の問題？直線の方程式から行列式まで駆け抜けろ！（ABC181 C - Collinearity）

♪ジングルベ～ル、ジングルベ～ル、お正～月～、今日は～楽しい、大み～そか、
ヘイヘイヘイ…

さて、いま、聴きたい曲はどっち？
・紅組…マライアキャリーのあの曲
・白組…ワムのラストなんちゃら

と、「年越しにクリスマス・ソングをかける馬鹿がどこにいるんですか？」と言った
ピストン西沢さんの名言を思い出しつつ、この記事を書いています。

この記事は、Competitive Programming (1) Advent Calendar 2020に参加しています。
https://adventar.org/calendars/4969

今回、使う問題はこちら、
ABC181 C - Collinearity

はい、このように、ぼくが、本番のコンテストで正解できなかった問題です。
そんなぼくが、今回は、水先案内人となり、

この問題を肴に、中学の1次関数から、高校の幾何学を抜けて大学の線形代数まで、
一気に航海します。

みなさん、泥船に乗った気分で楽しんでいただければ、幸いです。
（いま、船沈むと、海寒いぞ！）

問題概要
$N$個の点の中の相異なる3点であって、同一直線上にあるものは存在するでしょうか？
Yesか、Noかで、お答えください。
（$N$は、$3$以上、$100$以下。各点の$x$, $y$座標は、$-1000$から、$+1000$まで）

さて、A,B問題とは違い、本格的に計算量の吟味が必要になってくるのが、C問題。
まず、C問題に欠かせないお約束、計算量をチェックしましょう。

for (int i = 0; i < N; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        for (int k = j + 1; k < N; k++)
        {

            // （ここに、判定条件が入ります。）

            if (？？？？？) // もし、点i, j, kが一直線にあるのなら
            {
                WriteLine("Yes");
                ReadKey();
                return;
            }
        }
    }
}

通常は、避けようとする、3重ループですが、所詮、相手の$N$は、高々$100$個。
$100 × 100 × 100$ でも、たったの $1,000,000$通りで、
計算量的には、まったく問題ありません。

勝負は、判定条件にあると見てよさそうです。（←負けた。）

さて、点I, J, Kの3点が、一直線にあることを「正確に」判定するには、
どうすればいいのでしょうか？

以下、

また、以下、数式部分は、すべて、なんと新型コロナの影響につき（?）
ほぼ、すべて、手書きとなります。

★図形と方程式コース★
まず、直線と聞いて浮かぶのは、
$y=mx+n$の式ですが、（中学校時代だと、$y = ax + b$）

この時代の考え方では、正解にたどり着くのは、難しそうです。
$m$の傾きを求めるのは、中学、高校と一緒ですが…

関係ありそうな公式を一気に導いてみます。

ここまで導くのは、数学的に、もちろん正しいです。

ただ、ここで、2つ大問題があります。
「割り算があるじゃん」（※コンピュータだって、割り算は苦手です。）
「$x_{\rm I} = x_{\rm J}$ のとき、どうするの？」

後者は、高校数学で、ちゃんと解決策が示されていますが、
もっと問題なのは、前者の方。

整数÷整数が、整数とは限らない。
代数学的に言うと、「整数は除法について閉じていない。」
ことが、

小数点以下の小さな誤差となって、われわれを苦しめます。
（Multiplicationなんちゃら、と言っただけで、苦味を感じている人も多いはず。）

これは、シンプルなこの方法で、対処することが可能です。

分母を払った$Ax+By+C=0$も、やはり直線の方程式で、しかも、$x_{\rm I} = x_{\rm J}$のときも使えます。

for (int i = 0; i < N; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        var a = y[j] - y[i];
        var b = x[i] - x[j];
        var c = x[i] * y[j] - x[j] * y[i];
        for (int k = j + 1; k < N; k++)
        {
            if (a * x[k] + b * y[k] + c == 0)
            {
                WriteLine("Yes");
                return;
            }
        }
    }
}

WriteLine("No");

この方法で、ちゃんと正解が取れます。

★もうちょっと、かっこいい方法でやりたいんですが…★
ただ、ぼく、こんなことも書きました。

昨日のABC181のC問題。

「直線の方程式を作る」という考え方に行ってたのが、
マズかった。

各点を始点Iとして、他の2点J、Kとの
2本の「位置ベクトル」で、
行列式 = 0になるものがあるかどうかを、
確かめるっていうのが、

大学で線形代数を学んだ人の回答のはずですわーね。#AtCoder

— たかはしよしぴろ @ 誰も知らない存在理由 (@TheYoshipiro) November 2, 2020

for (int i = 0; i < N; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        var x1 = x[j] - x[i];
        var y1 = y[j] - y[i];
        for (int k = j + 1; k < N; k++)
        {
            var x2 = x[k] - x[i];
            var y2 = y[k] - y[i];
            var det = x1 * y2 - y1 * x2;
            if (det == 0)
            {
                WriteLine("Yes");
                ReadKey();
                return;
            }     
        }
    }
}

WriteLine("No");