Problem 252

252 Convex Holes

Problem 252 – Project Euler

計算幾何の問題.

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

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

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

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

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

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

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

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

さらに,幾何アルゴリズムは例外処理(場合分け)がとても煩雑.

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

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

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

これなら,前処理いらないから,気が楽.

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

コード(パスは答えから,ピリオドを抜いたもの(パスワードにピリオドが使えなかった!))

http://firestorage.jp/download/cf0e6fe882495b87b748484a7fa012e4eea9f18b

More Reading
Older// 計算幾何