Problem 252

252 Convex Holes

計算幾何の問題．

二次元平面上に点集合が与えられる．

最大空凸包とでもいうのでしょうか？

凸包であって，内部に他の点を含まないもの

のうちの最大面積を求める問題．

さて，どこから手を付ければ良いのやら…

とりあえず，はじめに思い浮かんだのは，点集合を三角形分割して，

そこから内部が空な凸包を構成する，という方法．

ただ，三角形分割という前処理をするのが気にくわない．

さらに，幾何アルゴリズムは例外処理（場合分け）がとても煩雑．

しかし，他に方法も思い付かなかったので，少し実装してみたが，バグが多すぎた．

そこで，二次元凸包は比較的簡単に求められることを思い出し，

そのアルゴリズムをちょっと変えれば良いのでは，と思った．

これなら，前処理いらないから，気が楽．

でHaskellで実装したらかなりシンプルになった．型宣言やimport文いれても無理せずに30行．

コード（パスは答えから，ピリオドを抜いたもの（パスワードにピリオドが使えなかった！））

コンテンツ