gistfile1.py

# Euler 184

import math



class Point:
	def __init__(self, x, y):
		self.x = x
		self.y = y
	
	def __mul__(self, o):
		"The k of cross product."
		return self.x * o.y - self.y * o.x
	
	def __sub__(self, o):
		return Point(self.x - o.x, self.y - o.y)



class Triangle:
	def __init__(self, a, b, c):
		self.a = a
		self.b = b
		self.c = c

	def __contains__(self, p):
		"""Point in triangle? From
		http://www.blackpawn.com/texts/pointinpoly/default.html"""

		for v1, v2, v3 in ((self.b-self.a, self.c-self.a, p-self.a),
					   (self.c-self.b, self.a-self.b, p-self.b),
					   (self.a-self.c, self.b-self.c, p-self.c)):
			
			d1 = v1 * v3
			if d1 == 0:
				return False

			d2 = v1 * v2
			if d2 == 0:
				return False

			if d2 * d1 < 0:
				return False

		return True



# -- test --

p1 = Point(1,2)
p2 = Point(-1,2)

px = Point(0,0)

# print p1 * p2

pn = p2 - p1
# print "p2 - p1 = ", pn.x, pn.y

p1 = Point(1,1)
p2 = Point(-1,1)
p3 = Point(0,-1)

t1 = Triangle(p1, p2, p3)

""" Fires 100,000 rounds in 6 seconds!
for i in range(100000):
	Point(0,0) in t1
"""
# -- end test --



radius = 3
width = (radius * 2) - 1
max_points = width ** 2
points = []


# Get points in the circle

for x in range(-width/2, width/2 + 1):
	for y in range(-width/2, width/2 + 1):
		if math.sqrt(x**2 + y**2) < radius:
			points.append(Point(x,y))

print "num points:", len(points)

number_of_triangles_with_origin = 0

# TODO - remove duplicates and symmetric triangles
for p1 in points:
	for p2 in points[points.index(p1):]:
		for p3 in points[points.index(p2):]:
			if Point(0,0) in Triangle(p1,p2,p3):
				number_of_triangles_with_origin += 1

print "triangles in center:", number_of_triangles_with_origin