Problem 163

http://projecteuler.net/index.php?section=problems&id=163
三角形の数を数える簡単なお仕事。
そんなに簡単ではないが。

m = 36

layer n = tail.concat $ [map (<+>(6*n-k,k)) grid| k<-[0,6..6*n]]++[[(6*(n+1),0)]]
    where grid = [(4,-2),(0,3),(0,6),(2,2),(3,0),(3,3)]
onLine x y = any (prallel (x <-> y)).map head.line $ x <%> 6
    where prallel (a,b) (c,d) = a*d==b*c

gridOnLine x = filter (not.null).map (lg x).line $ x <%> 6
    where lg x = tail.takeWhile inner.scanl (<+>) x.cycle

inner (x,y) = y>=0 && x+y<=6*m

triangle a = [(b,c)| [l,k]<- comb 2 $ gridOnLine a,b<-l, c<-k,onLine b c]

main = print.sum.map (length.triangle).((0,0):).concatMap layer $ [0..m-1]

comb 0 _ = [[]]
comb _ [] = []
comb (n+1) (x:xs) = map (x:) (comb n xs) ++ comb (n+1) xs

(<+>) (a,b) (c,d) = (a+c,b+d)
(<->) (a,b) (c,d) = (a-c,b-d)
(<%>) (a,b) c = (mod a c,mod b c)
                
line (0,0) = [[(0,3)],
              [(2,2),(1,1),(1,1),(2,2)],
              [(3,0)],
              [(4,-2),(2,-1),(2,-1),(4,-2)],
              [(3,-3)],
              [(2,-4),(1,-2),(1,-2),(2,-4)]]
line (0,3) = [[(0,3)],
              [(2,-1),(4,-2),(4,-2),(2,-1)]]
line (2,2) = [[(1,1),(1,1),(2,2),(2,2)],
              [(4,-2),(4,-2),(2,-1),(2,-1)],
              [(1,-2),(1,-2),(2,-4),(2,-4)]]
line (3,0) = [[(3,0)],
              [(1,-2),(2,-4),(2,-4),(1,-2)]]
line (4,4) = [[(2,2),(2,2),(1,1),(1,1)],
              [(2,-1),(2,-1),(4,-2),(4,-2)],
              [(2,-4),(2,-4),(1,-2),(1,-2)]]
line (3,3) = [[(1,1),(2,2),(2,2),(1,1)],
              [(3,-3)]]

座標変換（正三角形を直角二等辺三角形に）して格子点の座標が整数になるようにした。
格子点の種類が割り算のあまりでわかる。
まあ、全探索ですが、計算量が良く分からないなぁ。
問題の状況では格子点は約4000個（プログラムによると）
三角形かどうかチェックした格子点の組の数は約10^7個（プログラムによると）
だから、格子点の数に関して2乗ぐらい？（根拠がないなー）