sasaharayuugo.net

ジュニア算数オリンピック 二次元上のユークリッド幾何の問題 その21

ジュニア算数オリンピックにおけるユークリッド幾何学の問題の解答の自動化を模索している。まず三角形定理ループを回し、回答できなかったら1ステップの作図を試していって、それらで回答できるか探る。それでも駄目だったら2ステップ、3ステップと増やしていく。交点の確認はこの方法を使う。
 

 

06年度トライアル問題 問題9

『図の四角形ABCDはAB=BC=CDで、角B=168度、角C=108度です。角Dの大きさを求めなさい。


最終的な目標はプログラミングみたいに記述することなんだが、まあ前みたいにできるまで繰り返そうと思う。まずは全体の流れをハッキリさせてからだろう。
ちなみに、現在の問題点は2つで、一つは問題文の記述で、ネガティブな角を含むクラスタが情報として必要になる問題がこれから出てくるか。
もう一つは、角の和を取得する方法にクラスタがあるが、クラスタを見つけるには角の和が必要なこと。言い換えれば、主に辺の和から1つの点に辺が伸びている以外に、角の和を取得する方法は無いのかだ。


では、初期条件。

graph := [
        A : [
            [[B], []],
            [[D], []]
        ]
        ,
        B : [
            [[A], []],
            [[C], []]
        ]
        ,
        C : [
            [[B], []],
            [[D], []]
        ]
        ,
        D : [
            [[A], []],
            [[C], []]
        ]
    ];

    parallel_lines_lst := [
    ];

    triangle_lst := [
    ];

    cluster_lst := [
        [[A, B, C, D], [BAD_p, AB, ABC_p, BC, BCD_p, CD, ADC_p, AD]]
    ];

    always {
        ABC_p == 168;
        BCD_p == 108;
        AB == BC == CD;
    }


まずは角のイコールを確認する。
parallel_lines_lstには何も無い。
graphを確認して、どのkeyのvalueも2つ以上の、[0]も[1]も「!= 」のが無いので、対頂角は無し。valueの順番が関係無い組み合わせで確認したいのだけど、まあできる機能はあるだろう。

辺のイコールは定義どおりなので、新しく確認はしない。

辺の和を確認する。
graphを確認して、それぞれvalueの中身をfor文で調べて、[0]と[1]が「!= 」だったら、その[0]と[1]のそれぞれのfor文の組み合わせで、辺の和を追加していく。



triangle_lstを更新する。
graphを確認して、keyのvalueの中身で更にgraphを確認し、その中にkeyのvalueの中身と同じものがあれば、それらは三角形だ。



graphに着目して、辺にそのまま辺が当たっていて、足したら180°になるものを辺の和として登録する。
三角形に着目して、辺が更に反対側に伸びていたら、外角として登録する。
辺の和とtriangle_lstに着目して、もう一方の点が共有されていたら、登録する。



cluster_lstを更新する。
三角形はそのまま登録する。
更にクラスタ同士で辺を共有していて
それが三角形で直線で繋がっていたら、クラスタ
「角の一方 + 角のもう一方 == それらの角の共有していない辺同士の角 and それらの角の共有していない辺同士の角 <= 180」だったら、クラスタ

クラスタだと分かった後の角の和だとかの判定方法も詳しく考える必要がある。



いや、全体の流れをハッキリさせることに集中することにした。
 




「全体の話」
・記録1だとかで後戻りする
・アルゴリズムクイックリファレンスを参考にする
・答えを調べて達しているか



「点と点を結んで線にする」
graphを調べて、繋がっていないkeyと繋ぐ
・既存の角を割る動作でもあるはず
 全ての辺と辺の角の、ポジティブかネガティブを割る。
 クラスタを確認して、あれば、ポジティブを割っている
 割ったのがポジティブなら、生まれるのもポジティブ
 割った角がポジティブかネガティブか分からない時は、alwaysに条件式を作って、分かり次第確定するようにする

・三角形リストも調べることで更新する
・交点の判断は、クラスタ以外では三角関数が無ければ分からないのでは



「点と点の距離の分だけ線を延長」
graphを調べていって、辺のもう片方が無ければ、延長できる
・追加する点はアルファベット順に
・元々の辺がクラスタの一部なら、割る辺はネガティブ。結果は180とポジティブ
・イコールなので定義も追加する
・そういえば、辺の和も追加する必要があるな

・「手元で簡単に、1点から3辺が伸びている図を描いてみると、そういうのが3種類発生するはず

"BAD_p" + "DAE_p" == "BAE_h";
"BAD_p" + "BAE_h" == "DAE_n";」

・交点の判断は三角関数



「2点と、その間の垂直線とどこか1辺の交点による、二等辺三角形の作図」
三角形を調べていく
・追加する点はアルファベット順に
・2角を調べて、角度が小さい方と交わる。1つの三角形で3通り発生する
・「if "ABD_p" > "BAD_p" {~~~} elif ~~~」という具合か。
・「"BAD_p" + "ADB_p" + 132 == 180」から、「"BAD_p" < 48」を出せれば良いが。

・graphを更新する
・クラスタとして分割する
 割る角はポジティブ
 cluster_lst
・定義を追加する

・クラスタも調べれるが、とりあえずは調べない



「ある1辺と同じ長さの辺を別の辺に落とすことによる二等辺三角形の作図」
三角形を調べていく
・追加する点はアルファベット順に
・2角を調べて、両方が90°以下の時に
・今度は角度が大きい方の辺で作れるのでは。1つの三角形で3通り確認する



「クラスタの貼り合わせ」
クラスタを調べていく
・同じ長さの辺があれば
・それに対応するように複製し
・その重ね合わせる所にそのまま入り込むように、逆にしたり循環させたり
・重なり合う角の足し算がそれぞれポジティブであれば、そのままクラスタに登録
 




で、問題はやはり、クラスタと角の和と交点。

平面という概念があると、いわゆる何が嬉しいか、を考えると、まず角の和を考える時に、2つの角の1辺が隣接していたとして、「隣接していない辺同士の角 > 一方の角 and 隣接していない辺同士の角 > もう一方の角」で、判定できることだろう。平面という概念が無ければ、「隣接していない辺同士の角 == 一方の角 + もう一方の角」である必要がある。
あと、これは今朝気付いたんだが、三角関数を判定する時に、3Dだと上の角度以外の全ての情報が揃っていても、交点が発生するか考えることができないのではないか。
(あとは、四角形のクラスタかを判定する時に、繋がっている全ての辺を底辺と捉えて三角形で無ければ、全ての角がポジティブな四角形のクラスタだと言える。)
この2つの点で障害というか必要性が出れば、やはり平面という概念を導入することになるだろう。

その平面の嬉しさを抜きにしてネガティブな角を持つクラスタを考えると、区切って全ての角がポジティブだったら普通のクラスタだと見なせるというような、クラスタの前段階のようなものになるんじゃないか。そういう問題に出くわさないと分からないが。


角の和は、一辺を共有していて、「隣接していない辺同士の角 == 一方の角 + もう一方の角」という、つまりクラスタの片方バージョンのような条件というか定義になるわけだが、これ自体が角の和を含んでいるわけで、クラスタで角から辺に伸びていた時だとかに、クラスタから角の和という順番で考えるだけで良いのではないか。


あと、やっぱり圧倒的に問題のサンプルが足りていないという感じがしている。他の問題でも、必要な角の和が初期状態から弾き出せるのか試してみるつもりだ。