anta1 https://blog.hatena.ne.jp/anta1/ antaの競技プログラミング練習日記 https://anta1.hatenadiary.org/ SRM 幾何 辞書順最小 問題 Editorial 問題 (凸とは限らない)単純多角形の三角形分割を、辞書順最小でしろ。 引かれた対角線と多角形は、始点・終点以外で交差や触れてはならない 解答 まず、適当に対角線をひいても、三角形分割ができなくなることはない。つまり単純な辞書順greedyでおｋ。 あとは適当に「既に引いた対角線と交差せず」「多角形自身と交差せず」「多角形の内側にある」かどうかを判定したい。 これは整数幾何でがんばる コメント コードのコメントのとおり、「多角形の内側にある」判定で適当なことをしているが、Practice Roomのrng_58さんの解答では面積に着目しているようだ。 コード #incl… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fanta1.hatenadiary.org%2Fentry%2F20121221%2F1356080838" title="SRM 225 DIV1 Hard Triangulation - antaの競技プログラミング練習日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-12-21 18:07:18 rich https://anta1.hatenadiary.org/entry/20121221/1356080838 1.0 100%