# Euler Solution 102

### From ProgSoc Wiki

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[0],ps[1]), Point(ps[2],ps[3]), Point(ps[4],ps[5]) ) if t.contains(p): count+=1 print "Count: ", count