Three distinct points are plotted at random on a Cartesian plane, for which , , 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 ‘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’.
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.
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.
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 = 0for 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 + 1print(contained)main()