# Euler Solution 102

Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

## Python by Althalus

Runtime: 41ms

Wow. year 10 mathematics. Although, not exactly an application I would have ever imagined, back then. It's been so long since I did geometry, I had to look up how to calculate a line's equation from two points...

```data = [ .... ]

class Line2:
def __init__(self,p1, p2):
a = p2.y -p1.y
b = p2.x - p1.x
gcd = GCD(a,b)
self.a,self.b = -a/gcd,b/gcd
self.c = -(self.a*p1.x+self.b*p1.y)
def eval(self,p):
return self.a*p.x+self.b*p.y+self.c
def sameSide(self,p1,p2):
if self.eval(p1) > 0 and self.eval(p2) > 0: return True
if self.eval(p1) < 0 and self.eval(p2) < 0: return True
return False

def GCD(a,b):
while b != 0:
tmp = a % b
a,b = b,tmp
return a

class Point:
def __init__(self,x,y):
self.x,self.y = float(x), float(y)

class Triangle:
def __init__(self,a,b,c):
self.a,self.b,self.c = a,b,c
def contains(self,p):
if Line2(self.a,self.b).sameSide(self.c,p):
if Line2(self.c,self.b).sameSide(self.a,p):
if Line2(self.a,self.c).sameSide(self.b,p):
return True
return False

p = Point(0,0)
count = 0
for ps in data:
t = Triangle(
Point(ps,ps),
Point(ps,ps),
Point(ps,ps)
)
if t.contains(p): count+=1
print "Count: ", count
```