Problem 252

252 Convex Holes
Problem 252 - Project Euler
計算幾何の問題.
二次元平面上に点集合が与えられる.
最大空凸包とでもいうのでしょうか?
凸包であって,内部に他の点を含まないもの
のうちの最大面積を求める問題.
さて,どこから手を付ければ良いのやら…
とりあえず,はじめに思い浮かんだのは,点集合を三角形分割して,
そこから内部が空な凸包を構成する,という方法.


ただ,三角形分割という前処理をするのが気にくわない.
さらに,幾何アルゴリズムは例外処理(場合分け)がとても煩雑.
しかし,他に方法も思い付かなかったので,少し実装してみたが,バグが多すぎた.


そこで,二次元凸包は比較的簡単に求められることを思い出し,
そのアルゴリズムをちょっと変えれば良いのでは,と思った.
これなら,前処理いらないから,気が楽.

Haskellで実装したらかなりシンプルになった.型宣言やimport文いれても無理せずに30行.
コード(パスは答えから,ピリオドを抜いたもの(パスワードにピリオドが使えなかった!))
http://firestorage.jp/download/cf0e6fe882495b87b748484a7fa012e4eea9f18b