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

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

More Reading
Newer// Problem 229
Older// 千葉