凸包
http://karetta.jp/article/blog/oneline/011330
アルゴリズムはググッたから分かったんだけど、書けない。ギブアップだ。
(追記)
http://karetta.jp/article/blog/oneline/011485
答え見ちゃったんでアレなんだけど、一応さらします。ちゃんと動いているのか、今ひとつ分かりませんが。
(追追記)
ちゃんと動いてないな...
-- 凸包 import Data.List (sortBy) appTuple :: (a -> c) -> (b -> d) -> (a,b) -> (c,d) appTuple f g (x,y) = (f x, g y) type Vec a = (a,a) vsub :: Num a => Vec a -> Vec a -> Vec a vsub x = appTuple (fst x -) (snd x -) type Point = Vec Double ang :: Point -> Double ang (x,y) = if x >= 0 then if y >= 0 then atan (y/x) else 2 * pi + atan (y/x) else pi + atan (y/x) angle :: Point -> Point -> Double angle x y = if a < 0 then a + pi else a where a = ang (vsub y x) exec :: [Point] -> [Point] exec xs = exec' (head rightBottom) rightBottom where exec' x xs = let (y:ys) = sortP x xs in f x y [x] ys rightBottom = sortBy (\x y -> if snd x /= snd y then snd x `compare` snd y else fst y `compare` fst x) xs f :: Point -> Point -> [Point] -> [Point] -> [Point] f base start ret xs | base == start = ret | otherwise = let (y:ys) = sortP start xs in f base y (ret ++ [start]) ys sortP start = sortBy (\x y -> (angle start x) `compare` (angle start y))