tokoharu-sakura https://blog.hatena.ne.jp/tokoharu-sakura/ とこはるのまとめ https://tokoharuland.hateblo.jp/ ネット環境がよい場所に来たので書きます。 日本語が合っているかはよくわかりませんがどうぞ。 問題概要 平面上の格子点にn個の点があって、凸5角形が何個作れるか。 ただし任意の三点は同一直線上に存在しない n 解法 求めるのは、5点選んでそれの凸包が5点で構成されるもの。 したがって、5点選んで凸包が4点または3点で構成されるものを数え上げることが出来れば答えを求めることができる。まず、４点の凸包のものについて考えてみる。 選んだ5点で、「ある3点で三角形を作り、内部に1点、外部に1点存在する」ようなものは2通りある。 次に3点の凸包のあるものについて考えてみる。 これも同様に 選んだ5点で、「… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftokoharuland.hateblo.jp%2Fentry%2F2012%2F12%2F28%2F201907" title="xmas contest 2012 G問題について - とこはるのまとめ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/t/tokoharu-sakura/20121228/20121228201400.png Hatena Blog https://hatena.blog 2012-12-28 20:19:07 rich https://tokoharuland.hateblo.jp/entry/2012/12/28/201907 1.0 100%