プロジェクトオイラー
http://projecteuler.net/index.php
Q163.
省略
三角形内の点を生成する。その点から伸びる線を2本選ぶ。一方の線上で三角形内の点から伸びる線と他方の線との交点を求める。それが三角形内ならカウントする。
from itertools import count, combinationsdef make_point(n):
pt = ( (0, 0), (3, 0), (6, 0), (2, 2), (0, 3), (3, 3), (0, 6) )
s = set()
for y0 in range(0, n * 6, 6):
for x0 in range(0, n * 6 - y0, 6):
for dx, dy in pt:
x, y = x0 + dx, y0 + dy
s.add( (x, y))
for y0 in range(6, n * 6, 6):
for x0 in range(6, n * 6 + 6 - y0, 6):
for dx, dy in pt:
x, y = x0 - dx, y0 - dy
s.add( (x, y))
return list(s)def get_type(x, y):
mod_y = y % 6
mod_x = x % 6
if mod_y == 0:
if mod_x == 0:
return 0
elif mod_x == 3:
return 1
elif mod_x == 0:
if mod_y == 3:
return 2
elif mod_x == mod_y:
if mod_x == 3:
return 3
elif mod_x == 2:
return 4
elif mod_x == 4:
return 5
return -1def intersect(x1, y1, v1, x2, y2, v2):
a = v1[0]
b = -v2[0]
c = v1[1]
d = -v2[1]
D = a * d - b * c
if D == 0:
return (-1, -1)
else:
dx = x2 - x1
dy = y2 - y1
s = (d * dx - b * dy) / D
t = (-c * dx + a * dy) / D
return (v1[0] * s + x1, v1[1] * s + y1)def count_triangles(n):
v_ary = [
( (3, 0), (1, 1), (0, 3), (-1, 2), (-1, 1), (-2, 1) ), # 0, 0
( (3, 0), (-1, 2) ), # 3, 0
( (0, 3), (-2, 1) ), # 0, 3
( (1, 1), (-3, 3) ), # 3, 3
( (1, 1), (-1, 2), (-2, 1) ), 2, 2
( (1, 1), (-1, 2), (-2, 1) ) # 4, 4
]
counter = 0
a = [ ]
for x, y in make_point(n):
type = get_type(x, y)
v = v_ary[type]
for va, vb in combinations(v, 2):
for m in count(1):
x2 = x + m * va[0]
y2 = y + m * va[1]
if not is_inside(x2, y2, n):
break
type2 = get_type(x2, y2)
if type2 == -1:
continue
for vc in v_ary[type2]:
if va[0] * vc[1] - va[1] * vc[0] == 0:
continue
x3, y3 = intersect(x, y, vb, x2, y2, vc)
if is_inside(x3, y3, n):
if va[0] * (y3 - y2) - va[1] * (x3 - x2) > 0:
counter += 1
return counterdef is_inside(x, y, n):
return 0 <= x and 0 <= y and x + y <= n * 6N = 36
print count_triangles(N)
