How to solve the Project Euler triangle containment problem

Problem

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

Consider the following two triangles:

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

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

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

Using triangles.txt, a 27K text file that contains the coordinates of one thousand random triangles, find the number of triangles for which the interior contains the origin ‘O’.

Solution

The first step to solving this problem is to divide a triangle, say, ABC, into 3 parts: AOB, AOC, BOC.

The second step is to see if the sum of the areas of these three triangles is equal to the area of ABC. If it is, we can say that the origin ‘O’ lies inside ABC and vice versa.

The area of the triangles can be found by the following formula.

Area=12(xAxC)(yByA)(xAxB)(yCyA)Area = \frac{1}{2}|(x_A - x_C)(y_B - y_A) - (x_A - x_B)(y_C - y_A)|

Problem Diagram

The program below is an implementation of the algorithm in Python. It considers every triangle present in triangle.txt, calculates all the required areas, checks if the containment condition holds, counts the number of triangles for which it does, and finally outputs the number.

main.py
triangle.txt
def calculate_area (A, B, C):
return 0.5 * abs((A[0] - C[0]) * (B[1] - A[1]) - (A[0] - B[0]) * (C[1] - A[1]))
def contains_O (AOB, BOC, AOC, ABC):
return ABC == (AOB + BOC + AOC)
def main ():
file = open('triangle.txt', 'r').readlines()
origin = [0, 0]
contained = 0
for line in file:
line = line.strip('\n').split(',')
line = [int(i) for i in line]
area_ABC = calculate_area(line[0:2], line[2:4], line[4:6])
area_AOB = calculate_area(line[0:2], origin, line[2:4])
area_AOC = calculate_area(line[0:2], origin, line[4:6])
area_BOC = calculate_area(line[2:4], origin, line[4:6])
if contains_O(area_AOB, area_BOC, area_AOC, area_ABC):
contained = contained + 1
print(contained)
main()

Free Resources