Tag Archives: vectors

Euler Problem 102 – Vectors

This one was really interesting because so far, I haven’t seen very many Euler Project problems based on vector algebra. My solution is predicated on the theorem that if a point P is inside triangle ABC, then Area PAB + Area PBC + Area PAC = Area ABC

Visually, you can easily see how this works. This one is inside:

And this one is outside:

And there is a Wikipedia article on triangles that covers area calculations using vectors:

http://en.wikipedia.org/wiki/Triangle#Using_vectors

Note I had to calculate a delta value and test if its below a cut-off value (0.1 in this case). This is due to rounding errors in the math class. I could have played with decimal class precision, but calculating a delta is simple and it works.

import math
class Problem:
    def Area (self, P1, P2, P3):
        V1 = [P1[0]-P2[0],P1[1]-P2[1]]
        V2 = [P1[0]-P3[0],P1[1]-P3[1]]
        return float(.5)*math.sqrt((self.Mag(P1,P2)**2)*(self.Mag(P1,P3)**2)-(self.Dot(V1,V2)**2))
    def Mag (self, V1, V2):
        return math.sqrt(((V2[0]-V1[0])**2)+((V2[1]-V1[1])**2))
    def Dot (self, V1, V2):
        return (V1[0]*V2[0])+(V1[1]*V2[1])
    def Solution(self):
        count = 0
        P = [0,0]
        T = []
        f = open("triangles.txt", "r")
        for row in f.readlines():
            c = row.split(",")
            for i in [0,1,2,3,4,5]:
                c[i] = int(c[i])
            T.append(c)
        f.close()
        for t in T:
            A = [t[0],t[1]]
            B = [t[2],t[3]]
            C = [t[4],t[5]]
            sum = self.Area(P,A,B)+self.Area(P,B,C)+self.Area(P,A,C)
            delta = abs(self.Area(A,B,C)-sum)
            if delta < 0.1:
                count += 1
            print count,A,B,C,sum,self.Area(A,B,C),delta
        print "Answer =", count
if __name__ == '__main__':
    P = Problem()
    P.Solution()