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

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

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

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

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

今回、使う問題はこちら、
**ABC181 C - Collinearity**
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/cbe268b9-0cfd-09c9-ed22-d81606d1cf2c.png)

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

この問題を肴に、中学の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点が、一直線にあることを**「正確に」判定**するには、
どうすればいいのでしょうか？

以下、
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/67ab64b4-1335-2f46-1b1b-8e0bb1089d6e.png)

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

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

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/50f6ae60-fea1-dda5-8f4c-d3a8acb4b23f.png)

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

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

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

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

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/2a6631b5-0b7f-aeb9-2758-9ea608387cdc.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/dd7f43fc-4328-4490-9d6c-7ac46e3891e5.png)

分母を払った$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");
```

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

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

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">昨日のABC181のC問題。<br><br>「直線の方程式を作る」という考え方に行ってたのが、<br>マズかった。<br><br>各点を始点Iとして、他の2点J、Kとの<br>2本の「位置ベクトル」で、<br>行列式 = 0になるものがあるかどうかを、<br>確かめるっていうのが、<br><br>大学で線形代数を学んだ人の回答のはずですわーね。<a href="https://twitter.com/hashtag/AtCoder?src=hash&amp;ref_src=twsrc%5Etfw">#AtCoder</a></p>&mdash; たかはしよしぴろ @ 誰も知らない存在理由 (@TheYoshipiro) <a href="https://twitter.com/TheYoshipiro/status/1323269058930700289?ref_src=twsrc%5Etfw">November 2, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

「位置ベクトル」というのは、平たく言うと、数学的に扱いやすいように、
ある一点を原点 $(0, 0)$に持ってくる方法を指します。

そして、その位置ベクトルが

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/4d0042bf-37a7-0285-4a19-977486ce2d4b.png)

となるとき、ベクトルIJとIKは平行で、点I, J, Kは、一直線にあることがわかります。

ここで、方針が2つ。

1. x, yは、どうせ、1000までの整数なのだから、最小公倍数で処理をする
2. 2本のベクトルが平行だから、その2本のベクトルがなす、平行四辺形の面積は0になるはず…(←！)

1番目の解き方の方が、たぶん、簡単な気がするのですが、
2番目の解き方の方が、言っているツイートの解き方です。
ただ、あまり、思いつかないと思いますが、行列式をいじっていると思いつきはします。

ここで、ベクトルの解き方を、ホントにザーッと式だけで、紹介します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/78f12f06-2afe-7fb0-bc80-92be0523e856.png)

さて、そこそこ手間がかかる計算がありましたが、
これは、さっきのツイートでいった行列式で処理をするのと、**実は一緒の答え**です。

なぜなら、**（2次の）行列式を計算するということ自体が、
平行四辺形の面積を求めること、**
そのものだから。

ということを、平行四辺形の面積を求めることから考えられる、
行列式の条件を要請していきながら、示していきたいと思います。
（書き方も大学チックな書き方にしているのは、ご了承のほどを）

**【いちおう、行列式の定義】**
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/ab236de0-a46e-3723-af83-51e3d8d2ae38.png)

まず、
**【要請1】**
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/11297941-0b31-2da5-5973-f2aaa25e5cc0.png)

そりゃあ、底辺1、高さ1で、しかも、なす角が直角な、
1辺が1の正方形は、面積1であって、欲しいですよね。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/58f32818-f1d9-986a-1ca6-c7fa1e31200f.png)


【要請2】
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/6ac5b89d-9448-d4b1-dd30-865cdbe72fee.png)

上の式については、下の図を参照。
下の式については、下の図を回転させたり、pとかqとか文字を入れ替えたりしてみてください。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/fafbe7dc-07c6-3ce7-889a-911f4753f3cb.png)

【要請3】
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/1261b8ec-354e-8065-41b1-bdc9f2d41c41.png)

つまらない要請のように聞こえますが、
あとでじんわり効いて来ます。

【要請4】
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/30429bb6-2e87-2536-2730-11a3ec3682f1.png)

例えば、上の式の
左辺（下左図のピンクの平行四辺形の面積）
＝右辺（下右図の青と緑の平行四辺形の面積の合計）
になってることは、おわかりいただけるでしょうか？

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/1993acd0-988c-6450-74e7-b5d49a999f48.png)

さて、以上、あたりまえのことを要請してきたつもりですが、
残念な事実があります。

この式の計算をご覧ください。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/fbb72bd7-b0ca-22ef-fd85-4e8512f30706.png)

面積を求めるはずなのに、マイナスの値が出てきました。

ただ、これも認めることにします。
（この問題で欲しいのは、面積が0かどうかだけなので、）

では、2本のベクトルIJ、IKの面積を求めるべく、
行列式の計算してみたいと思います。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/5c8842e7-8810-3abb-70cd-72a044a2da9e.png)

ベクトルで求めたときの平行四辺形の面積が求まりました。
（ただ、こっちは、符号のプラス、マイナスの違いがある可能性だけはありますが。）

```
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");
```

このコード、もちろん、ちゃんとAC取れます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/485903/b1eb3708-f22a-8abd-30d3-78af26c62194.png)
https://atcoder.jp/contests/abc181/submissions/17844407


以上で、中学から、大学までの幾何学のつながりを、
なんとか描くことができました。

そして、Advent Calendar
**Competitive Programming (1) Advent Calendar 2020**
https://adventar.org/calendars/4969
も、**クリスマスまでに間に合わせることは別にして、**
年内に間に合わせることができました。

上記、Advent Calenderの最後を飾ることができました、
25人全員の記事を上げることができました。
25人の執筆陣を**勝手に**代表して、読者の皆様に感謝いたします。

それでは、みなさん、来年もよいお年を。（12/31 23:53記す。）