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

Count how many of 1000 triangles contain the origin (0,0). Uses the cross-product sign test. We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

    Set count <- 0
    For each each (A, B, C) in triangles:
        Set d1 <- A.x * B.y - B.x * A.y
        Set d2 <- B.x * C.y - C.x * B.y
        Set d3 <- C.x * A.y - A.x * C.y
        Set has_neg <- (d1 < 0) or (d2 < 0) or (d3 < 0)
        Set has_pos <- (d1 > 0) or (d2 > 0) or (d3 > 0)
        If not (has_neg and has_pos) then
            Set count <- count + 1
    Return 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