Project Euler

Obtuse Angled Triangles

Consider the set S(r) of points (x, y) with integer coordinates satisfying |x| + |y| <= r. Let O = (0, 0) and C = (r/4, r/4). Let N(r) be the number of points B in S(r) such that triangle OBC has a...

Source sync Apr 19, 2026

Problem #0210

Level Level 10

Solved By 1,985

Languages C++, Python

Answer 1598174770174689458

Length 255 words

geometrymodular_arithmeticbrute_force

Consider the set $S(r)$ of points $(x,y)$ with integer coordinates satisfying $|x| + |y| \le r$.

Let $O$ be the point $(0,0)$ and $C$ the point $(r/4,r/4)$.

Let $N(r)$ be the number of points $B$ in $S(r)$, so that the triangle $OBC$ has an obtuse angle, i.e. the largest angle $\alpha $ satisfies $90^\circ < \alpha < 180^\circ $.

So, for example, $N(4)=24$ and $N(8)=100$.

What is $N(1\,000\,000\,000)$?

Problem 210: Obtuse Angled Triangles

Analysis

Classifying Obtuse Angles

With $O = (0, 0)$ and $C = (r/4, r/4)$ , we determine which vertex has the obtuse angle using dot products.

Obtuse at $O$ : $\vec{OB} \cdot \vec{OC} < 0$

x \cdot \frac{r}{4} + y \cdot \frac{r}{4} < 0 \implies x + y < 0

Obtuse at $C$ : $\vec{CO} \cdot \vec{CB} < 0$

\left(-\frac{r}{4}\right)\left(x - \frac{r}{4}\right) + \left(-\frac{r}{4}\right)\left(y - \frac{r}{4}\right) < 0 \implies x + y > \frac{r}{2}

Obtuse at $B$ : $\vec{BO} \cdot \vec{BC} < 0$

(-x)\left(\frac{r}{4} - x\right) + (-y)\left(\frac{r}{4} - y\right) < 0 \implies x^2 + y^2 < \frac{r}{4}(x + y)

Completing the square:

\left(x - \frac{r}{8}\right)^2 + \left(y - \frac{r}{8}\right)^2 < \frac{r^2}{32}

This is a circle centered at $(r/8, r/8)$ with radius $r\sqrt{2}/8$ .

These Regions Are Disjoint

Region O requires $x + y < 0$ .
Region C requires $x + y > r/2$ .
Region B requires $(x - r/8)^2 + (y - r/8)^2 < r^2/32$ , which implies $0 < x + y < r/2$ .

So the three regions are pairwise disjoint.

Degenerate Cases

$O$ , $B$ , $C$ are collinear when $B$ lies on the line $y = x$ . These must be excluded from all counts.

Region O Count

Lattice points with $|x| + |y| \leq r$ and $x + y < 0$ , excluding $x = y$ :

By symmetry of the diamond about $x + y = 0$ :

|\text{Region O}| = \frac{\text{total} - \text{on } x+y=0}{2} - |\{x = y, x + y < 0\}|

The total lattice points in the diamond is $2r^2 + 2r + 1$ . Points on $x + y = 0$ : $r + 1$ . Points with $x + y < 0$ : $r(2r+1)/2$ . Points with $x = y$ and $x + y < 0$ : $r/2$ points.

|\text{Region O}| = r(2r+1)/2 - r/2 = r^2

Region C Count

By a similar counting argument over $x + y = s$ for $s > r/2$ :

|\text{Region C}| = \frac{r^2}{2}

Region B Count

Count lattice points $(x, y)$ with $(x - r/8)^2 + (y - r/8)^2 < r^2/32$ and $x \neq y$ .

Substituting $u = x - r/8$ , $v = y - r/8$ (for $r$ divisible by 8):

u^2 + v^2 < \frac{r^2}{32} = 2\left(\frac{r}{8}\right)^2

The circle count is computed by iterating over $u$ and counting valid $v$ .

Collinear points have $u = v$ : $2u^2 < r^2/32$ gives $|u| < r/8$ , yielding $r/4 - 1$ points.

Final Formula

N(r) = r^2 + \frac{r^2}{2} + \text{circle\_count} - \left(\frac{r}{4} - 1\right) = \frac{3r^2}{2} - \frac{r}{4} + 1 + \text{circle\_count}

where circle_count is computed in $O(r/8)$ time.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

Time: $O(r/8) \approx O(1.25 \times 10^8)$
Space: $O(1)$

Answer

\boxed{1598174770174689458}

C++ project_euler/problem_210/solution.cpp

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

int main() {
    // O = (0,0), C = (r/4, r/4), B = lattice point with |x|+|y| <= r
    // Count B where triangle OBC is obtuse.
    //
    // Three disjoint obtuse regions:
    // Region O (obtuse at O): x+y < 0, count = r^2
    // Region C (obtuse at C): x+y > r/2, count = r^2/2
    // Region B (obtuse at B): (x-r/8)^2+(y-r/8)^2 < r^2/32, x != y
    //   circle_count - collinear_count, where collinear = r/4 - 1
    //
    // N(r) = r^2 + r^2/2 + circle_count - (r/4 - 1)
    //       = 3r^2/2 - r/4 + 1 + circle_count

    long long r = 1000000000LL;
    long long s = r / 8; // 125000000, center of circle for region B

    // Region O + Region C
    // Use __int128 to avoid overflow
    typedef __int128 i128;
    i128 region_OC = (i128)r * r + (i128)r * r / 2; // 3r^2/2

    // Region B: circle centered at (s, s), radius^2 = R2 = r^2/32 = 2*s^2
    // Count lattice points (x,y) with (x-s)^2 + (y-s)^2 < R2
    // Equivalently, (u,v) = (x-s, y-s), count u^2+v^2 < R2 = 2*s^2

    long long R2 = 2LL * s * s; // = 2 * 125000000^2 = 31250000000000000

    // For each u from -max_u to max_u, count v with v^2 < R2 - u^2
    // max_u: u^2 < R2, |u| <= isqrt(R2 - 1)

    // isqrt function
    auto isqrt = [](long long n) -> long long {
        if (n < 0) return -1;
        long long q = (long long)sqrt((double)n);
        while (q * q > n) q--;
        while ((q + 1) * (q + 1) <= n) q++;
        return q;
    };

    long long max_u = isqrt(R2 - 1);

    i128 circle_count = 0;
    // Use symmetry: u and -u give same count, and swap u,v gives same count
    // circle_count = sum_{u=-max_u}^{max_u} (2*max_v(u) + 1)
    // By symmetry in u: = (2*max_v(0)+1) + 2*sum_{u=1}^{max_u} (2*max_v(u)+1)

    {
        // u = 0
        long long rem = R2;
        long long q = isqrt(rem);
        long long mv = (q * q == rem) ? q - 1 : q;
        circle_count += 2 * mv + 1;
    }

    for (long long u = 1; u <= max_u; u++) {
        long long rem = R2 - u * u;
        if (rem <= 0) break;
        long long q = isqrt(rem);
        long long mv = (q * q == rem) ? q - 1 : q;
        circle_count += 2 * (2 * mv + 1); // factor 2 for +u and -u
    }

    // Collinear points in circle: u = v, 2u^2 < R2 = 2s^2, so u^2 < s^2, |u| <= s-1
    // Count = 2*(s-1) + 1 = 2s - 1 = r/4 - 1
    i128 collinear = r / 4 - 1;

    i128 region_B = circle_count - collinear;
    i128 answer = region_OC + region_B;

    // Print __int128
    // Convert to string
    string result;
    i128 a = answer;
    if (a == 0) {
        result = "0";
    } else {
        bool neg = false;
        if (a < 0) { neg = true; a = -a; }
        while (a > 0) {
            result += ('0' + (int)(a % 10));
            a /= 10;
        }
        if (neg) result += '-';
        reverse(result.begin(), result.end());
    }
    cout << result << endl;

    return 0;
}

Python project_euler/problem_210/solution.py

"""
Problem 210: Obtuse Angled Triangles

S(r) = lattice points with |x|+|y| <= r. O = (0,0), C = (r/4, r/4).
Count B in S(r) such that triangle OBC is obtuse.

Three disjoint obtuse regions:
- Region O (obtuse at O): x+y < 0, count = r^2
- Region C (obtuse at C): x+y > r/2, count = r^2/2
- Region B (obtuse at B): (x-r/8)^2 + (y-r/8)^2 < r^2/32, x != y
  = circle_count - (r/4 - 1)

N(r) = 3r^2/2 + circle_count - r/4 + 1

Note: For r = 10^9, the circle loop has ~1.77*10^8 iterations.
This runs in ~2-3 minutes in Python (or a few seconds in C++).
"""

import math

def solve(r):
    assert r % 8 == 0

    region_OC = r * r + r * r // 2  # r^2 + r^2/2

    s = r // 8  # center coordinate
    R2 = 2 * s * s  # radius squared = r^2/32

    # Count lattice points (u,v) with u^2 + v^2 < R2
    max_u = math.isqrt(R2 - 1)

    circle_count = 0
    # u = 0
    rem = R2
    q = math.isqrt(rem)
    mv = q - 1 if q * q == rem else q
    circle_count += 2 * mv + 1

    # u = 1 to max_u, counted twice (for -u)
    for u in range(1, max_u + 1):
        rem = R2 - u * u
        if rem <= 0:
            break
        q = math.isqrt(rem)
        mv = q - 1 if q * q == rem else q
        circle_count += 2 * (2 * mv + 1)

    collinear = r // 4 - 1
    region_B = circle_count - collinear

    answer = region_OC + region_B
    return answer

# For r = 10^9, this takes a few minutes in Python.
# Uncomment the line below to run (or use the C++ version for speed).
r = 10**9
print(solve(r))