Problem 102: Triangle Containment

Mathematical Development

Definition. For points $U = (u_x, u_y)$, $V = (v_x, v_y)$, $W = (w_x, w_y)$ in $\mathbb{R}^2$, define the signed area function:

Equivalently, $\sigma(U, V, W) = \frac{1}{2}\det\!\begin{pmatrix} v_x - u_x & w_x - u_x \\ v_y - u_y & w_y - u_y \end{pmatrix}$.

Theorem 1 (Point-in-Triangle via Signed Areas). Let $A, B, C$ be the vertices of a non-degenerate triangle and let $P$ be a point in $\mathbb{R}^2$. Then $P$ lies in the interior of $\triangle ABC$ if and only if $\sigma(A, B, P)$, $\sigma(B, C, P)$, and $\sigma(C, A, P)$ all have the same nonzero sign.

Proof. The directed edge $\overrightarrow{AB}$ partitions $\mathbb{R}^2 \setminus \ell_{AB}$ into two open half-planes, where $\ell_{AB}$ is the line through $A$ and $B$. The sign of $\sigma(A, B, P)$ determines in which half-plane $P$ lies: positive if $P$ is to the left of $\overrightarrow{AB}$ (counterclockwise side), negative if to the right.

If $\triangle ABC$ has counterclockwise orientation ($\sigma(A, B, C) > 0$), then the interior equals the intersection of the three left half-planes defined by $\overrightarrow{AB}$, $\overrightarrow{BC}$, $\overrightarrow{CA}$. Hence $P$ is interior if and only if $\sigma(A, B, P) > 0$, $\sigma(B, C, P) > 0$, and $\sigma(C, A, P) > 0$.

If $\triangle ABC$ has clockwise orientation ($\sigma(A, B, C) < 0$), the interior is the intersection of the three right half-planes, and all three signed areas are negative. In both cases, $P$ is interior if and only if all three signed areas share the same nonzero sign. $\blacksquare$

Lemma 1 (Simplification for $P = O$). When $P = (0, 0)$ is the origin, the half-plane tests reduce to cross products of position vectors:

Proof. Substituting $P = (0, 0)$ into the signed area formula:

which is the $z$-component of $\vec{OA} \times \vec{OB}$. $\blacksquare$

Corollary. The origin lies inside $\triangle ABC$ if and only if the three quantities $a_x b_y - b_x a_y$, $b_x c_y - c_x b_y$, and $c_x a_y - a_x c_y$ are all strictly positive or all strictly negative.

Proof. Immediate from Theorem 1 and Lemma 1, noting that multiplication by 2 preserves sign. $\blacksquare$

Editorial

Each triangle can be tested independently by looking only at orientation signs. For vertices $A$, $B$, and $C$, the quantities $A \times B$, $B \times C$, and $C \times A$ are the signed areas of the triangles formed with the origin. If these three values are all nonnegative or all nonpositive, then the origin lies inside the triangle (or on its boundary); if both positive and negative signs occur, the origin must lie outside.

That reduces the problem to a straight scan of the data file. For every triangle we compute three determinants, apply the sign test, and increment the answer when the origin passes the test.

Pseudocode

Set the count to zero.

For each triangle with vertices A, B, and C:
    Compute the signed areas of OAB, OBC, and OCA.
    If these three values do not mix positive and negative signs:
        Increase the count.

Return the count.

Complexity Analysis

• Time. $O(N)$ where $N = 1000$ is the number of triangles. Each triangle requires three cross-product computations and three comparisons, all $O(1)$.
• Space. $O(1)$ auxiliary. Each triangle is processed independently.

Answer

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;

/*
 * Problem 102: Triangle Containment
 *
 * Test whether the origin lies inside each triangle using the
 * cross-product sign method: compute the z-components of
 * OA x OB, OB x OC, OC x OA and check that all share the same sign.
 */

bool contains_origin(int x1, int y1, int x2, int y2, int x3, int y3) {
    long long d1 = (long long)x1 * y2 - (long long)x2 * y1;
    long long d2 = (long long)x2 * y3 - (long long)x3 * y2;
    long long d3 = (long long)x3 * y1 - (long long)x1 * y3;
    bool has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    bool has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
    return !(has_neg && has_pos);
}

int main() {
    ifstream fin("p102_triangles.txt");
    istream& in = fin.is_open() ? fin : cin;

    int count = 0;
    string line;
    while (getline(in, line)) {
        if (line.empty()) continue;
        replace(line.begin(), line.end(), ',', ' ');
        istringstream iss(line);
        int x1, y1, x2, y2, x3, y3;
        if (iss >> x1 >> y1 >> x2 >> y2 >> x3 >> y3) {
            if (contains_origin(x1, y1, x2, y2, x3, y3))
                count++;
        }
    }

    cout << count << endl;
    return 0;
}

"""
Problem 102: Triangle Containment

Count how many of 1000 triangles contain the origin (0,0).
Uses the cross-product sign test.
"""
import os
import urllib.request


def contains_origin(x1, y1, x2, y2, x3, y3):
    d1 = x1 * y2 - x2 * y1
    d2 = x2 * y3 - x3 * y2
    d3 = x3 * y1 - x1 * y3
    has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)
    return not (has_neg and has_pos)


def get_data():
    local_file = os.path.join(os.path.dirname(os.path.abspath(__file__)),
                              "p102_triangles.txt")
    if os.path.exists(local_file):
        with open(local_file) as f:
            return f.read()
    url = "https://projecteuler.net/resources/documents/0102_triangles.txt"
    response = urllib.request.urlopen(url)
    data = response.read().decode("utf-8")
    with open(local_file, "w") as f:
        f.write(data)
    return data


def solve():
    data = get_data()
    count = 0
    for line in data.strip().split("\n"):
        x1, y1, x2, y2, x3, y3 = map(int, line.strip().split(","))
        if contains_origin(x1, y1, x2, y2, x3, y3):
            count += 1
    return count


if __name__ == "__main__":
    answer = solve()
    print(answer)
    assert answer == 228