← Problem 101

Triangle containment

Problem 103 →

Triangle containment

Problem 102

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.
NOTE: The first two examples in the file represent the triangles in the example given above.
from math import acos, sqrt, pi
from tools import load_data_table_integers


def prod(a, b):
    return sum(a[i] * b[i] for i in range(2))


def gamma(a, b):
    return acos(prod(a, b) / sqrt(prod(a, a) * prod(b, b)))


def run():
    data = load_data_table_integers(102, delimiter=',')

    total = 0
    for line in data:
        a = line[0:2]
        b = line[2:4]
        c = line[4:6]
        if gamma(a, b) + gamma(b, c) + gamma(c, a) > 2 * pi - 1e-10:
            total += 1

    return total