Problem 228

Project Euler Haskell

228 Minkowski Sums
Problem 228 - Project Euler
ミンコフスキー和を求める問題．
一般の図形のミンコフスキー和を求めるのは難しいが…
今回は，凸な図形でしかも，かなり，かたちが綺麗．
整数演算で大丈夫なので，計算誤差も心配ない．

import Data.Set (unions, size, fromAscList)
import Data.Ratio ((%))

p228 :: (Integral a) => a -> a -> Int
p228 m n = size.unions.map polygon $ [m..n]
    where polygon k = fromAscList [ l % k | l <- [0..k - 1]]

main :: IO ()
main = print $ p228 1864 1909

もう少し効率化できそうな気配があるが，十分はやいので良しとする．