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