Problem 228

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 <- [..k - 1]]
main :: IO ()
main = print $ p228 1864 1909

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