競プロ日記

特にnext_combinationはすごい。

蟻本読んでちょっと感動した。
1年前に蟻本買っててよかったと思ったね。

別に数学的にすごいことをしているわけではないけど、確かにその操作したら組み合わせを列挙できるよね、という感じ。

早くbit演算でなにか実装してみたい気持ちが強かった。

そこでこの問題。

対角線の長さ計算を一度に抑えて、選んだ三角形ごとに持ってこれないかな、と考えていたらbitが使えるんじゃないかと。
頂点の組み合わせのbitをキーにしたmapに保存し、うまくループを回せばできそうだと考えた。

結局ACできなかったからbit演算部分が合っているか分からないものの、bitを利用した実装を経験できたのは経験値としてでかい。

四角形の面積は、四角形を半分に割ってそれぞれヘロンの公式を使って足そうという考え。
・・・だったのだが、そもそも凹ならそれじゃ計算できない。
割り方によって正しい答えと間違った答えが出る。
ということに書き終わった後に気づいたので第2作。





コード②
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3298517#1

もはやbitをキーにしたmapである必要はないが名残ということで。
今回は先程の気づきを活かし、三角形に分けて四角形の面積を求めた場合、分け方によって違いが出れば凹、という方針。
三角形の面積は、先程と同様ヘロンの公式を使って求めた。
誤差を減らせるように割り算や平方根を減らしたつもりだが、それでも誤差があるのかACには至らなかった。
そこでEPSを使って誤差を打ち消そうとしたのだが、それでもACには至らない。
辺の長さの計算に平方根を使っているとは言え、そこまで誤差が出るのだろうか。
どこかでコードを間違っているような気がしなくもない。





コード③
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3298582#1

どんどんコードが短くなっていく。
そもそもヘロンの公式なんて使わなくても良かったのではな方針。
外積使えば面積出せるじゃんに気づいて割り算平方根なく誤差なく気持ちよくAC。
外積が負の値も取れるとか、そもそも外積どうやって出すんだっけとか色々忘れてて苦労した。





今回の収穫は、bit演算の経験と、数学的知識使えば簡単正確に書けるねってこと。
地味に作り始めたライブラリにヘロンの公式も追加しておいた。
コード②に関しては、誤差の影響がどの程度なのか分からないものの、実装としては間違ってないと思っているので、全然違うだろって部分あったら教えてほしいです。