Problem 163: Cross-hatched Triangles

Mathematical Development

Definitions

Definition 1. A cross-hatched equilateral triangle of size $n$ is the figure obtained by overlaying 6 families of lines on an equilateral triangle with side length $n$.

Definition 2. In oblique coordinates $(u, v)$ where the main triangle has vertices $(0,0)$, $(n,0)$, $(0,n)$ and interior $\{(u,v) : u \geq 0,\; v \geq 0,\; u + v \leq n\}$, a line $\ell$ is specified by an equation $au + bv = c$ with integer coefficients.

Theorem 1 (Line families). The 6 line families in the cross-hatched triangle of size $n$ are:

All six direction vectors are pairwise non-parallel.

Proof. Families $F_1$—$F_3$ are the standard triangular grid at unit spacing. Families $F_4$—$F_6$ arise from the cross-hatching: the medians and their translates from each vertex to the midpoints of segments on the opposite side. The direction vectors $(1,0)$, $(0,1)$, $(1,1)$, $(1,-1)$, $(1,2)$, $(2,1)$ are pairwise non-parallel (no pair is a scalar multiple of the other), which can be verified by checking that all $\binom{6}{2} = 15$ cross-products $a_i b_j - a_j b_i$ are nonzero. $\square$

Theorem 2 (Triangle formation criterion). Three lines $\ell_1, \ell_2, \ell_3$ from three distinct families form a non-degenerate triangle if and only if:

1. The three families have pairwise distinct directions (guaranteed since all 6 directions are distinct).
2. The three lines are not concurrent.
3. All three pairwise intersection points lie within or on the boundary of the main triangle.

Proof. Two lines from the same family are parallel and cannot form a triangle edge. Three lines from three distinct non-parallel families intersect pairwise in three points, forming a triangle if and only if the three points are distinct (equivalently, the lines are not concurrent). The triangle is valid only if it lies within the main figure, which requires all three vertices to satisfy $u \geq 0$, $v \geq 0$, $u + v \leq n$. $\square$

Lemma 1 (Rational intersection). The intersection of line $a_1 u + b_1 v = c_1$ from family $F_i$ and line $a_2 u + b_2 v = c_2$ from family $F_j$ ($i \neq j$) is the point:

All quantities are integers, and the denominator $D = a_1 b_2 - a_2 b_1 \neq 0$.

Proof. By Cramer’s rule applied to the $2 \times 2$ system. The determinant is nonzero since the directions are non-parallel. $\square$

Lemma 2 (Containment test). A point $(p/d, q/d)$ with $d > 0$ lies in the closed main triangle if and only if $p \geq 0$, $q \geq 0$, and $p + q \leq nd$.

Proof. Substituting into the inequalities $u \geq 0$, $v \geq 0$, $u + v \leq n$ and clearing the positive denominator. $\square$

Lemma 3 (Concurrency test). Three lines are concurrent if and only if the intersection of the first two equals the intersection of the first and third. In rational coordinates $(p_1/d_1, q_1/d_1)$ and $(p_2/d_2, q_2/d_2)$, this is $p_1 d_2 = p_2 d_1$ and $q_1 d_2 = q_2 d_1$.

Proof. Direct from the uniqueness of intersection points in distinct directions. $\square$

Editorial

The code works directly with the six line families from the mathematical model. Any triangle in the cross-hatched figure is determined by choosing one line from each of three distinct families, so the search becomes a finite enumeration over family triples and parameter values inside those families.

For each selected triple of lines, the program computes the three pairwise intersections using exact rational arithmetic, not floating point. That avoids accidental merging or separation of vertices that should be identical. A candidate is counted exactly when all three intersection points lie inside the main triangle and the three lines are not concurrent. Since the entire configuration at size 36 is still small enough, this brute-force geometric test is fast and completely reliable.

Pseudocode

List the six line families together with every valid parameter value for size 36.
Initialize the triangle count to zero.

For each choice of three distinct families:
    For each line from the first family:
        For each line from the second family:
            Compute their intersection exactly.
            If this point lies outside the main triangle, skip the branch.

            For each line from the third family:
                Compute the other two pairwise intersections.
                Skip the triple if either point lies outside the main triangle.
                Skip it again if the three lines are concurrent.
                Otherwise count one triangle.

Return the total count.

Complexity Analysis

Time. There are $\binom{6}{3} = 20$ family triples. For each triple, the three nested loops iterate over $O(n)$ lines each, giving $O(n^3)$ intersection tests per triple. Total: $O(20 \cdot n^3)$. For $n = 36$: approximately $20 \cdot 37^3 \approx 10^6$ tests.

Space. $O(n)$ for line parameter storage, $O(1)$ working space per test.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Project Euler Problem 163: Cross-hatched Triangles
 *
 * Count triangles in a cross-hatched equilateral triangle of size n = 36.
 * Six line families in oblique coordinates; enumerate all C(6,3) = 20
 * family triples and all line triples, checking containment and
 * non-concurrency via exact integer arithmetic.
 */

int main() {
    const int n = 36;

    int a[6] = {1, 0, 1, 1, 1, 2};
    int b[6] = {0, 1, 1, -1, 2, 1};

    vector<vector<int>> lines(6);
    for (int k = 0; k <= n; k++) lines[0].push_back(k);
    for (int k = 0; k <= n; k++) lines[1].push_back(k);
    for (int k = 0; k <= n; k++) lines[2].push_back(k);
    for (int k = -(n - 1); k <= n - 1; k++) lines[3].push_back(k);
    for (int k = 1; k <= 2 * n - 1; k++) lines[4].push_back(k);
    for (int k = 1; k <= 2 * n - 1; k++) lines[5].push_back(k);

    long long total = 0;

    for (int f1 = 0; f1 < 6; f1++) {
        for (int f2 = f1 + 1; f2 < 6; f2++) {
            for (int f3 = f2 + 1; f3 < 6; f3++) {
                int a1 = a[f1], b1 = b[f1];
                int a2 = a[f2], b2 = b[f2];
                int a3 = a[f3], b3 = b[f3];

                int d12 = a1 * b2 - a2 * b1;
                int d13 = a1 * b3 - a3 * b1;
                int d23 = a2 * b3 - a3 * b2;
                if (d12 == 0 || d13 == 0 || d23 == 0) continue;

                for (int c1 : lines[f1]) {
                    for (int c2 : lines[f2]) {
                        long long nu12 = (long long)c1 * b2 - (long long)c2 * b1;
                        long long nv12 = (long long)a1 * c2 - (long long)a2 * c1;
                        long long dd12 = d12;
                        if (dd12 < 0) { nu12 = -nu12; nv12 = -nv12; dd12 = -dd12; }
                        if (nu12 < 0 || nv12 < 0 || nu12 + nv12 > (long long)n * dd12)
                            continue;

                        for (int c3 : lines[f3]) {
                            long long nu13 = (long long)c1 * b3 - (long long)c3 * b1;
                            long long nv13 = (long long)a1 * c3 - (long long)a3 * c1;
                            long long dd13 = d13;
                            if (dd13 < 0) { nu13 = -nu13; nv13 = -nv13; dd13 = -dd13; }
                            if (nu13 < 0 || nv13 < 0 || nu13 + nv13 > (long long)n * dd13)
                                continue;

                            long long nu23 = (long long)c2 * b3 - (long long)c3 * b2;
                            long long nv23 = (long long)a2 * c3 - (long long)a3 * c2;
                            long long dd23 = d23;
                            if (dd23 < 0) { nu23 = -nu23; nv23 = -nv23; dd23 = -dd23; }
                            if (nu23 < 0 || nv23 < 0 || nu23 + nv23 > (long long)n * dd23)
                                continue;

                            // Non-concurrency: P12 != P13
                            if (nu12 * dd13 == nu13 * dd12 && nv12 * dd13 == nv13 * dd12)
                                continue;

                            total++;
                        }
                    }
                }
            }
        }
    }

    cout << total << endl;
    return 0;
}

"""
Project Euler Problem 163: Cross-hatched Triangles

Count triangles in a cross-hatched equilateral triangle of size n = 36.

Six line families in oblique coordinates (u, v) with triangle
u >= 0, v >= 0, u + v <= n.  A triangle is formed by choosing one line
from each of three distinct families; we check containment and
non-concurrency via exact rational arithmetic.
"""


def solve():
    n = 36

    families = [(1, 0), (0, 1), (1, 1), (1, -1), (1, 2), (2, 1)]
    line_ranges = [
        list(range(0, n + 1)),
        list(range(0, n + 1)),
        list(range(0, n + 1)),
        list(range(-(n - 1), n)),
        list(range(1, 2 * n)),
        list(range(1, 2 * n)),
    ]

    def intersect(a1, b1, c1, a2, b2, c2):
        det = a1 * b2 - a2 * b1
        if det == 0:
            return None
        nu = c1 * b2 - c2 * b1
        nv = a1 * c2 - a2 * c1
        d = det
        if d < 0:
            nu, nv, d = -nu, -nv, -d
        return (nu, nv, d)

    def inside(nu, nv, d):
        return nu >= 0 and nv >= 0 and nu + nv <= n * d

    total = 0
    for f1 in range(6):
        a1, b1 = families[f1]
        for f2 in range(f1 + 1, 6):
            a2, b2 = families[f2]
            for f3 in range(f2 + 1, 6):
                a3, b3 = families[f3]
                for c1 in line_ranges[f1]:
                    for c2 in line_ranges[f2]:
                        p12 = intersect(a1, b1, c1, a2, b2, c2)
                        if p12 is None or not inside(*p12):
                            continue
                        for c3 in line_ranges[f3]:
                            p13 = intersect(a1, b1, c1, a3, b3, c3)
                            if p13 is None or not inside(*p13):
                                continue
                            p23 = intersect(a2, b2, c2, a3, b3, c3)
                            if p23 is None or not inside(*p23):
                                continue
                            nu1, nv1, d1 = p12
                            nu2, nv2, d2 = p13
                            if nu1 * d2 == nu2 * d1 and nv1 * d2 == nv2 * d1:
                                continue
                            total += 1

    print(total)


solve()