Project Euler Problem 102 Solution

Project Euler Problem 102 Statement

Three distinct points are plotted at random on a Cartesian plane, for which $-1000 \le x, y \le 1000$, such that a triangle is formed.

Consider the following two triangles:

\begin{gather} A(-340,495), B(-153,-910), C(835,-947)\\ X(-175,41), Y(-421,-714), Z(574,-645) \end{gather}

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.

Solution

HackerRank Project Euler Problem 102 overview:

You are given co-ordinates of $N$ "random" triangles, find the number of triangles for which the interior contains the origin.

Solution Summary

Geometric principle: A point $P$ (the origin in this case) lies inside a triangle $ABC$ if and only if $P$ is on the same side of each of the three edges $AB$, $BC$, and $CA$. Checking the sign of cross products between vectors originating at $P$ helps determine which “side” of an edge $P$ is on. If all the signs are the same we ensure that $P$ is consistently in the same orientation (clockwise or counterclockwise) relative to each pair of vertices.

Solution Detail

Python Source Code

n = 0
for line in range(int(input())):
    ax, ay, bx, by, cx, cy = map(int, input().split())
    a = ax*by - ay*bx > 0
    b = bx*cy - by*cx > 0
    c = cx*ay - cy*ax > 0
    n+= a==b==c

print(n)

1. Reading Input

The code reads an integer (the number of triangles), then for each triangle, it reads 6 integers:

ax, ay = coordinates of vertex A
bx, by = coordinates of vertex B
cx, cy = coordinates of vertex C

2. The Cross Product Test

The expressions
ax * by - ay * bx, bx * cy - by * cx, and cx * ay - cy * ax use the cross product of vectors originating at the origin (O = (0,0)).

The cross product of two vectors $ \vec{OA} $ and $ \vec{OB} $ is given by: $ \vec{OA} \times \vec{OB} = ax \cdot by - ay \cdot bx $.
Its sign tells us the rotation direction:

Positive: counterclockwise
Negative: clockwise

Thus, in the code:

$a = (ax \cdot by - ay \cdot bx > 0)$ is True if $ \vec{OA} $ to $ \vec{OB} $ is counterclockwise.
$b = (bx \cdot cy - by \cdot cx > 0)$ is True if $ \vec{OB} $ to $ \vec{OC} $ is counterclockwise.
$c = (cx \cdot ay - cy \cdot ax > 0)$ is True if $ \vec{OC} $ to $ \vec{OA} $ is counterclockwise.

3. Checking If the Origin Is Inside the Triangle

After computing a, b, and c, the line n+= a == b == c checks if all three boolean values are the same (either all True or all False).

Geometrically, a point $ O $ (the origin) is inside triangle $ ABC $ if and only if $ O $ is on the same side of each of the triangle’s edges $ AB, BC, CA $. In terms of cross products:

All positive ( $ > 0 $ ) means the origin is "rotated around" counterclockwise by the triangle.
All negative ( $ < 0 $ ) means it’s rotated around clockwise.

Hence, if $a == b == c$, it implies $O$ is strictly inside the triangle.

4. Final Count

Each time $a == b == c$ is True, the counter n is incremented. After reading all triangles, we print n to get the count of how many triangles contain the origin.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 102

HackerRank Project Euler 102: You are given co-ordinates of $N$ "random" triangles, find the number of triangles for which the interior contains the origin.