Project Euler

Triangle Centres

Consider all non-degenerate triangles ABC with: All vertices at lattice points (integer coordinates). Circumcenter at the origin O = (0, 0), so all vertices lie on a circle x^2 + y^2 = R^2. Orthoce...

Source sync Apr 19, 2026

Problem #0264

Level Level 19

Solved By 693

Languages C++, Python

Answer 2816417.1055

Length 371 words

geometrymodular_arithmeticalgebra

Consider all the triangles having:

All their vertices on lattice points
Circumcentre at the origin $O$.
Orthocentre at the point $H(5, 0)$.

There are nine such triangles having a perimeter $\le 50$.

Listed and shown in ascending order of their perimeter, they are:

\columnseprule0pt

$A(-4, 3)$, $B(5, 0)$, $C(4, -3)$

$A(4, 3)$, $B(5, 0)$, $C(-4, -3)$

$A(-3, 4)$, $B(5, 0)$, $C(3, -4)$

$A(3, 4)$, $B(5, 0)$, $C(-3, -4)$

$A(0, 5)$, $B(5, 0)$, $C(0, -5)$

$A(1, 8)$, $B(8, -1)$, $C(-4, -7)$

$A(8, 1)$, $B(1, -8)$, $C(-4, 7)$

$A(2, 9)$, $B(9, -2)$, $C(-6, -7)$

$A(9, 2)$, $B(2, -9)$, $C(-6, 7)$

Problem illustration

The sum of their perimeters, rounded to four decimal places, is $291.0089$.

Find all such triangles with a perimeter $\le 10^5$.

Enter as your answer the sum of their perimeters rounded to four decimal places.

Problem 264: Triangle Centres

Mathematical Foundation

Theorem 1 (Euler’s relation for circumcenter and orthocenter). For a triangle inscribed in a circle centered at $O$ , the orthocenter $H$ satisfies

\vec{OH} = \vec{OA} + \vec{OB} + \vec{OC}.

Proof. Let $O$ be the circumcenter. For any vertex $A$ , the perpendicular from $A$ to $BC$ passes through $H$ . We show $\vec{AH} = \vec{OB} + \vec{OC}$ . Since $O$ is equidistant from $B$ and $C$ , $\vec{OB} + \vec{OC}$ is perpendicular to $\vec{BC}$ (as $(\vec{OB} + \vec{OC}) \cdot (\vec{OB} - \vec{OC}) = |\vec{OB}|^2 - |\vec{OC}|^2 = 0$ ). Also, $\vec{OB} + \vec{OC}$ starts from $O$ and ends at the point $B + C$ (relative to $O$ ). We need to verify that $A + (\vec{OB} + \vec{OC})$ lies on the altitude from $A$ . Since $\vec{AH} \perp \vec{BC}$ and $(\vec{OB} + \vec{OC}) \perp \vec{BC}$ , it suffices to check one case. Setting $H' = A + \vec{OB} + \vec{OC}$ , one verifies $\vec{BH'} \perp \vec{AC}$ analogously, confirming $H' = H$ . Therefore $\vec{OH} = \vec{OA} + \vec{OB} + \vec{OC}$ . $\square$

Corollary. With $O$ at the origin and $H = (5, 0)$ : $A + B + C = (5, 0)$ , i.e., $a_1 + b_1 + c_1 = 5$ and $a_2 + b_2 + c_2 = 0$ .

Lemma 1 (Line-circle reduction). Given vertex $A = (a_1, a_2)$ on $x^2 + y^2 = n$ , the constraint that $B$ and $C = (5 - a_1 - b_1, -a_2 - b_2)$ both lie on the same circle reduces to a line-circle intersection:

(2a_1 - 10) b_1 + 2a_2 \, b_2 = 10a_1 - 25 - n

combined with $b_1^2 + b_2^2 = n$ , yielding at most 2 solutions for $B$ .

Proof. From $|C|^2 = n$ : $(5 - a_1 - b_1)^2 + (a_2 + b_2)^2 = n$ . Expanding and using $a_1^2 + a_2^2 = n$ and $b_1^2 + b_2^2 = n$ , we get $(2a_1 - 10)b_1 + 2a_2 b_2 = 10a_1 - 25 - n$ . This is a line in the $(b_1, b_2)$ -plane, intersecting the circle $b_1^2 + b_2^2 = n$ in at most 2 points. $\square$

Lemma 2 (Discriminant condition). The discriminant of the resulting quadratic is $\Delta = 16 a_2^2 D$ where

D = n\bigl((2a_1 - 10)^2 + 4a_2^2\bigr) - (10a_1 - 25 - n)^2.

Integer solutions for $B$ exist only when $D$ is a non-negative perfect square.

Proof. Substituting the linear constraint into the circle equation $b_1^2 + b_2^2 = n$ and simplifying using standard quadratic-formula techniques. The factor $16a_2^2$ arises from the coefficient of the linear equation in $b_2$ . $\square$

Editorial

Algorithm: For each lattice point A = (a1, a2) with n = a1^2+a2^2, the orthocenter condition gives a LINEAR constraint on B = (b1, b2): (2a1 - 10)b1 + 2a2b2 = 10a1 - 25 - n Combined with b1^2 + b2^2 = n (same circle), this is a line-circle intersection with at most 2 solutions. The discriminant simplifies to D = n(L^2+4a2^2) - R^2, where L = 2a1-10 and R = 10*a1-25-n. D must be a non-negative perfect square. Each unordered triangle {A,B,C} is counted 6 times (3! orderings). There are 155 valid triangles. All have circumradius <= 20000.

Pseudocode

R_max = 20000 (perimeter <= 100000 implies R <= ~20000)
total_perimeter = 0

For a1 from -R_max to R_max:
    for a2 = 1 to R_max: (a2 > 0 by convention to avoid double-counting)
        n = a1^2 + a2^2
        If n == 0 then continue
        L = 2*a1 - 10
        M = 2*a2
        R_val = 10*a1 - 25 - n
        D = n*(L^2 + M^2) - R_val^2
        If D < 0 then continue
        sqrt_D = isqrt(D)
        If sqrt_D^2 != D then continue

        For each sign in {+1, -1}:
            b2_num = M*R_val + sign * L * sqrt_D
            b2_den = L^2 + M^2
            If b2_num % b2_den != 0 then continue
            b2 = b2_num / b2_den
            b1 = (R_val - M*b2) / L (if L != 0)
            If b1^2 + b2^2 != n then continue

            C = (5 - a1 - b1, -a2 - b2)
            if C on circle and triangle non-degenerate:
                perim = dist(A,B) + dist(B,C) + dist(A,C)
                If perim <= 100000 then
                    total_perimeter += perim

Return total_perimeter / 6 (each unordered triangle counted 6 times)

Complexity Analysis

Time: $O(R_{\max}^2)$ iterations over lattice points, each doing $O(1)$ arithmetic (integer square root test, quadratic solve). With $R_{\max} = 20000$ , this is $\sim 1.3 \times 10^9$ operations.
Space: $O(1)$ auxiliary space (no storage of intermediate results beyond running totals).

Answer

\boxed{2816417.1055}

C++ project_euler/problem_264/solution.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

/*
 * Problem 264: Triangle Centres
 *
 * Find all triangles ABC with:
 * - Integer coordinate vertices on circle x^2+y^2 = n (circumcenter at origin)
 * - Orthocenter at H(5,0): A+B+C = (5,0)
 * - Perimeter <= 100000
 * - Non-degenerate (positive area)
 *
 * Sum of all such perimeters, rounded to 4 decimal places.
 *
 * Key insight: for fixed A = (a1,a2) on x^2+y^2=n, the constraint
 * C = (5-a1-b1, -a2-b2) on the same circle gives:
 *   (2*a1-10)*b1 + 2*a2*b2 = 10*a1 - 25 - n
 * Combined with b1^2+b2^2 = n, this is a line-circle intersection
 * giving at most 2 solutions for B.
 *
 * The discriminant simplifies to D = n*(L^2+4*a2^2) - R^2 where
 * L = 2*a1-10, R = 10*a1-25-n. D must be a non-negative perfect square.
 *
 * Each unordered triangle counted 6 times (3! orderings).
 * Total: 155 triangles, sum of perimeters = 2816417.1055.
 *
 * Answer: 2816417.1055
 */

int main() {
    const double MAX_PERIMETER = 100000.0;
    const ll R_MAX = 20000LL;  // Sufficient: no triangles found beyond R=20000

    double total_perimeter = 0.0;
    ll triangle_count = 0;

    for (ll a1 = -R_MAX; a1 <= R_MAX; a1++) {
        ll L = 2*a1 - 10;
        ll max_a2_sq = R_MAX * R_MAX - a1 * a1;
        if (max_a2_sq < 0) continue;
        ll max_a2 = (ll)sqrtl((long double)max_a2_sq);
        while ((max_a2+1)*(max_a2+1) <= max_a2_sq) max_a2++;

        for (ll a2 = 1; a2 <= max_a2; a2++) {
            ll n = a1*a1 + a2*a2;
            ll R_val = 10*a1 - 25 - n;

            // D = n*(L^2+4*a2^2) - R_val^2. Must be a perfect square >= 0.
            lll D = (lll)n * ((lll)L*L + 4*(lll)a2*a2) - (lll)R_val * R_val;
            if (D < 0) continue;

            ll sq_D = (ll)sqrtl((long double)D);
            while ((lll)sq_D * sq_D < D) sq_D++;
            while ((lll)sq_D * sq_D > D) sq_D--;
            if ((lll)sq_D * sq_D != D) continue;

            // disc = 16*a2^2*D, sqrt(disc) = 4*a2*sq_D
            for (int a2_sign = -1; a2_sign <= 1; a2_sign += 2) {
                ll a2v = a2 * a2_sign;
                ll M = 2 * a2v;

                lll A_c = (lll)M*M + (lll)L*L;
                lll B_c = -2*(lll)R_val*(lll)L;
                ll sq_disc = 4 * a2 * sq_D;

                for (int sign = -1; sign <= 1; sign += 2) {
                    lll num = -B_c + sign * sq_disc;
                    lll denom = 2 * A_c;
                    if (denom == 0) continue;
                    if (num % denom != 0) continue;
                    ll b1 = (ll)(num / denom);

                    lll num2 = (lll)R_val - (lll)L * b1;
                    if (num2 % M != 0) continue;
                    ll b2 = (ll)(num2 / M);

                    if (b1*b1 + b2*b2 != n) continue;

                    ll c1 = 5 - a1 - b1;
                    ll c2 = -a2v - b2;
                    if (c1*c1 + c2*c2 != n) continue;

                    ll cross = (b1-a1)*(c2-a2v) - (b2-a2v)*(c1-a1);
                    if (cross == 0) continue;

                    double dAB = sqrt((double)((a1-b1)*(a1-b1)+(a2v-b2)*(a2v-b2)));
                    double dBC = sqrt((double)((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2)));
                    double dCA = sqrt((double)((c1-a1)*(c1-a1)+(c2-a2v)*(c2-a2v)));
                    double peri = dAB + dBC + dCA;

                    if (peri <= MAX_PERIMETER) {
                        total_perimeter += peri;
                        triangle_count++;
                    }
                }
            }
        }

        // Handle a2 = 0
        {
            ll n = a1*a1;
            if (n > 0) {
                ll R_val = 10*a1 - 25 - n;
                if (L == 0) {
                    // a1=5, n=25
                    for (ll bb1 = -5; bb1 <= 5; bb1++) {
                        ll bb2_sq = 25 - bb1*bb1;
                        if (bb2_sq < 0) continue;
                        ll bb2 = (ll)sqrt((double)bb2_sq);
                        if (bb2*bb2 != bb2_sq) continue;
                        for (int s = (bb2==0?1:-1); s <= 1; s += 2) {
                            ll b2v = s*bb2;
                            ll c1v = -bb1, c2v = -b2v;
                            if (c1v*c1v+c2v*c2v != 25) continue;
                            ll cross = (bb1-5)*c2v - b2v*(c1v-5);
                            if (cross == 0) continue;
                            double d1 = sqrt((double)((5-bb1)*(5-bb1)+b2v*b2v));
                            double d2 = sqrt((double)((bb1-c1v)*(bb1-c1v)+(b2v-c2v)*(b2v-c2v)));
                            double d3 = sqrt((double)((c1v-5)*(c1v-5)+c2v*c2v));
                            double peri = d1+d2+d3;
                            if (peri <= MAX_PERIMETER) {
                                total_perimeter += peri;
                                triangle_count++;
                            }
                        }
                    }
                } else if (R_val % L == 0) {
                    ll b1 = R_val / L;
                    ll b2_sq = n - b1*b1;
                    if (b2_sq >= 0) {
                        ll b2 = (ll)sqrt((double)b2_sq);
                        if (b2*b2 == b2_sq) {
                            for (int s = (b2==0?1:-1); s <= 1; s += 2) {
                                ll b2v = s*b2;
                                ll c1 = 5-a1-b1, c2 = -b2v;
                                if (c1*c1+c2*c2 != n) continue;
                                ll cross = (b1-a1)*c2 - b2v*(c1-a1);
                                if (cross == 0) continue;
                                double d1 = sqrt((double)((a1-b1)*(a1-b1)+b2v*b2v));
                                double d2 = sqrt((double)((b1-c1)*(b1-c1)+(b2v-c2)*(b2v-c2)));
                                double d3 = sqrt((double)((c1-a1)*(c1-a1)+c2*c2));
                                double peri = d1+d2+d3;
                                if (peri <= MAX_PERIMETER) {
                                    total_perimeter += peri;
                                    triangle_count++;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    total_perimeter /= 6.0;
    triangle_count /= 6;
    printf("%.4f\n", total_perimeter);
    return 0;
}

Python project_euler/problem_264/solution.py

"""
Problem 264: Triangle Centres

Find all triangles ABC with:
- All vertices have integer coordinates on circle x^2+y^2 = n
- Circumcenter at origin O(0,0)
- Orthocenter at H(5,0), which means A+B+C = (5,0)
- Perimeter <= 100000
- Non-degenerate (positive area)

Sum all such perimeters, rounded to 4 decimal places.

Algorithm:
For each lattice point A = (a1, a2) with n = a1^2+a2^2, the orthocenter
condition gives a LINEAR constraint on B = (b1, b2):
  (2*a1 - 10)*b1 + 2*a2*b2 = 10*a1 - 25 - n

Combined with b1^2 + b2^2 = n (same circle), this is a line-circle
intersection with at most 2 solutions.

The discriminant simplifies to D = n*(L^2+4*a2^2) - R^2, where
L = 2*a1-10 and R = 10*a1-25-n. D must be a non-negative perfect square.

Each unordered triangle {A,B,C} is counted 6 times (3! orderings).

There are 155 valid triangles. All have circumradius <= 20000.

Answer: 2816417.1055
"""

import math

def solve():
    MAX_PERIMETER = 100000.0
    R_MAX = 20000  # No triangles found beyond R=20000

    total_perimeter = 0.0
    triangle_count = 0

    for a1 in range(-R_MAX, R_MAX + 1):
        L = 2 * a1 - 10
        max_a2_sq = R_MAX * R_MAX - a1 * a1
        if max_a2_sq < 0:
            continue
        max_a2 = int(math.isqrt(max_a2_sq))

        for a2 in range(1, max_a2 + 1):
            n = a1 * a1 + a2 * a2
            R_val = 10 * a1 - 25 - n

            # D must be a non-negative perfect square
            D = n * (L * L + 4 * a2 * a2) - R_val * R_val
            if D < 0:
                continue

            sq_D = int(math.isqrt(D))
            if sq_D * sq_D != D:
                continue

            # Process both signs of a2
            for a2_sign in (-1, 1):
                a2v = a2 * a2_sign
                M = 2 * a2v

                A_c = M * M + L * L
                B_c = -2 * R_val * L
                sq_disc = 4 * a2 * sq_D

                for sign in (-1, 1):
                    num = -B_c + sign * sq_disc
                    denom = 2 * A_c
                    if denom == 0:
                        continue
                    if num % denom != 0:
                        continue
                    b1 = num // denom

                    num2 = R_val - L * b1
                    if num2 % M != 0:
                        continue
                    b2 = num2 // M

                    if b1 * b1 + b2 * b2 != n:
                        continue

                    c1 = 5 - a1 - b1
                    c2 = -a2v - b2
                    if c1 * c1 + c2 * c2 != n:
                        continue

                    cross = (b1 - a1) * (c2 - a2v) - (b2 - a2v) * (c1 - a1)
                    if cross == 0:
                        continue

                    dAB = math.sqrt((a1 - b1) ** 2 + (a2v - b2) ** 2)
                    dBC = math.sqrt((b1 - c1) ** 2 + (b2 - c2) ** 2)
                    dCA = math.sqrt((c1 - a1) ** 2 + (c2 - a2v) ** 2)
                    peri = dAB + dBC + dCA

                    if peri <= MAX_PERIMETER:
                        total_perimeter += peri
                        triangle_count += 1

        # Handle a2 = 0
        n = a1 * a1
        if n > 0:
            R_val = 10 * a1 - 25 - n
            if L == 0:
                # a1=5, n=25
                for bb1 in range(-5, 6):
                    bb2_sq = 25 - bb1 * bb1
                    if bb2_sq < 0:
                        continue
                    bb2 = int(math.isqrt(bb2_sq))
                    if bb2 * bb2 != bb2_sq:
                        continue
                    for s in ([-1, 1] if bb2 > 0 else [1]):
                        b2v = s * bb2
                        c1v, c2v = -bb1, -b2v
                        if c1v * c1v + c2v * c2v != 25:
                            continue
                        cross = (bb1 - 5) * c2v - b2v * (c1v - 5)
                        if cross == 0:
                            continue
                        d1 = math.sqrt((5 - bb1) ** 2 + b2v ** 2)
                        d2 = math.sqrt((bb1 - c1v) ** 2 + (b2v - c2v) ** 2)
                        d3 = math.sqrt((c1v - 5) ** 2 + c2v ** 2)
                        peri = d1 + d2 + d3
                        if peri <= MAX_PERIMETER:
                            total_perimeter += peri
                            triangle_count += 1
            elif R_val % L == 0:
                b1 = R_val // L
                b2_sq = n - b1 * b1
                if b2_sq >= 0:
                    b2 = int(math.isqrt(b2_sq))
                    if b2 * b2 == b2_sq:
                        for s in ([-1, 1] if b2 > 0 else [1]):
                            b2v = s * b2
                            c1, c2 = 5 - a1 - b1, -b2v
                            if c1 * c1 + c2 * c2 != n:
                                continue
                            cross = (b1 - a1) * c2 - b2v * (c1 - a1)
                            if cross == 0:
                                continue
                            d1 = math.sqrt((a1 - b1) ** 2 + b2v ** 2)
                            d2 = math.sqrt((b1 - c1) ** 2 + (b2v - c2) ** 2)
                            d3 = math.sqrt((c1 - a1) ** 2 + c2 ** 2)
                            peri = d1 + d2 + d3
                            if peri <= MAX_PERIMETER:
                                total_perimeter += peri
                                triangle_count += 1

        if a1 % 5000 == 0:
            print(f"a1={a1}, triangles={triangle_count//6}, sum={total_perimeter/6:.4f}", flush=True)

    total_perimeter /= 6.0
    triangle_count //= 6
    print(f"{total_perimeter:.4f}")

if __name__ == "__main__":
    solve()