問題 109 SCUD Busters
難易度 投稿数 4752 (正解率 30.7 %)

まだ解けていないが、いくつかのことをメモしておく。

最初は簡単に解ける問題だと思っていたが、やってみたらサンプル出力の値よりはずいぶん小さい結果しか得られなかったことに驚いた。

与えられた多角形内の点(家とか発電所)が必ずしも多角形の頂点でないことにやっと気づいた。そうでないと、2番目の王国(下図)の例でも判るように、国境線が定まらない。

「the area of a kingdom is the area enclosed by the minimal-perimeter thin wall.」 見落としがちな文章だが、凸包のことを言っていると思う。また、説明文に頂点のことを一言も言ってないのもこれで納得した。

<問題の整理>
複数の多角形P(多角形自体ではなく、それに含まれる点だけが与えられる)と、いくつかの点Aが与えられ、多角形の中から、Aを囲むものだけをピックアップし、それらの多角形の面積を求める問題。

<クリアすべきこと>
  1.点を囲む多角形を求める ← 凸包を求める
  2.点が多角形内にあるかどうかの判定 ← 解決済(アルゴリズムは本ブログに既出
  3.多角形の面積計算 ← 簡単にできる

<凸包を求めるアルゴリズム>
  平面上の点集合の凸包とは、その集合のすべての点を含む最小の凸多角形のこと。また、凸包とは点を囲む最短の閉路(つまり、点をすべて囲み、周長が最短なものは凸包という)。
  与えられたN個の点に対して、そのいくつかが凸多角形を作り、残りのすべての点はそれに含まれる。凸多角形の頂点となる点をみつけるのは、凸包を求めるアルゴリズムという。

サンプル入力にあった2番目の王国の国境線(つまり、5点を囲む凸包)

Comments are closed.

Post Navigation