TheAlgorithms-Python

1
"""
2
Three distinct points are plotted at random on a Cartesian plane,
3
for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.
4

5
Consider the following two triangles:
6

7
A(-340,495), B(-153,-910), C(835,-947)
8

9
X(-175,41), Y(-421,-714), Z(574,-645)
10

11
It can be verified that triangle ABC contains the origin, whereas
12
triangle XYZ does not.
13

14
Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text
15
file containing the coordinates of one thousand "random" triangles, find
16
the number of triangles for which the interior contains the origin.
17

18
NOTE: The first two examples in the file represent the triangles in the
19
example given above.
20
"""
21

22
from __future__ import annotations
23

24
from pathlib import Path
25

26

27
def vector_product(point1: tuple[int, int], point2: tuple[int, int]) -> int:
28
    """
29
    Return the 2-d vector product of two vectors.
30
    >>> vector_product((1, 2), (-5, 0))
31
    10
32
    >>> vector_product((3, 1), (6, 10))
33
    24
34
    """
35
    return point1[0] * point2[1] - point1[1] * point2[0]
36

37

38
def contains_origin(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> bool:
39
    """
40
    Check if the triangle given by the points A(x1, y1), B(x2, y2), C(x3, y3)
41
    contains the origin.
42
    >>> contains_origin(-340, 495, -153, -910, 835, -947)
43
    True
44
    >>> contains_origin(-175, 41, -421, -714, 574, -645)
45
    False
46
    """
47
    point_a: tuple[int, int] = (x1, y1)
48
    point_a_to_b: tuple[int, int] = (x2 - x1, y2 - y1)
49
    point_a_to_c: tuple[int, int] = (x3 - x1, y3 - y1)
50
    a: float = -vector_product(point_a, point_a_to_b) / vector_product(
51
        point_a_to_c, point_a_to_b
52
    )
53
    b: float = +vector_product(point_a, point_a_to_c) / vector_product(
54
        point_a_to_c, point_a_to_b
55
    )
56

57
    return a > 0 and b > 0 and a + b < 1
58

59

60
def solution(filename: str = "p102_triangles.txt") -> int:
61
    """
62
    Find the number of triangles whose interior contains the origin.
63
    >>> solution("test_triangles.txt")
64
    1
65
    """
66
    data: str = Path(__file__).parent.joinpath(filename).read_text(encoding="utf-8")
67

68
    triangles: list[list[int]] = []
69
    for line in data.strip().split("\n"):
70
        triangles.append([int(number) for number in line.split(",")])
71

72
    ret: int = 0
73
    triangle: list[int]
74

75
    for triangle in triangles:
76
        ret += contains_origin(*triangle)
77

78
    return ret
79

80

81
if __name__ == "__main__":
82
    print(f"{solution() = }")
83