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 May 21, 2026

Problem #0210

Level Level 10

Solved By 1,985

Languages C++, Python

Answer 1598174770174689458

Length 319 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

Mathematical Development

Classifying Obtuse Angles

With $O = (0, 0)$ and $C = (r/4, r/4)$ , we determine which vertex is obtuse by dot products.

Obtuse at $O$ :

\vec{OB} \cdot \vec{OC} < 0 \iff x \cdot \frac{r}{4} + y \cdot \frac{r}{4} < 0 \iff x + y < 0.

Obtuse at $C$ :

\vec{CO} \cdot \vec{CB} < 0 \iff \left(-\frac{r}{4}\right)\left(x - \frac{r}{4}\right) + \left(-\frac{r}{4}\right)\left(y - \frac{r}{4}\right) < 0 \iff x + y > \frac{r}{2}.

Obtuse at $B$ :

\vec{BO} \cdot \vec{BC} < 0 \iff (-x)\left(\frac{r}{4} - x\right) + (-y)\left(\frac{r}{4} - y\right) < 0 \iff x^2 + y^2 < \frac{r}{4}(x + y).

Completing the square gives

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

so the $B$ -obtuse region is an open disk centered at $(r/8, r/8)$ .

These Regions Are Disjoint

Region $O$ requires $x + y < 0$ .
Region $C$ requires $x + y > r/2$ .
Region $B$ implies $0 < x + y < r/2$ .

Hence the three obtuse cases are pairwise disjoint.

Degenerate Cases

The points $O$ , $B$ , and $C$ are collinear exactly when $B$ lies on the line $y = x$ . These points must be excluded because they do not form a genuine triangle.

Region O Count

Inside the diamond $|x| + |y| \leq r$ , the condition $x + y < 0$ cuts off exactly half of the non-boundary points, and removing the collinear points on $y = x$ leaves

|\text{Region } O| = r^2.

Region C Count

A parallel counting argument on the strips $x + y = s$ for $s > r/2$ gives

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

Region B Count

Write

u = x - \frac{r}{8}, \qquad v = y - \frac{r}{8}.

Because $r = 10^9$ is divisible by 8, this is an integer translation, and the disk becomes

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

Thus Region $B$ contributes the number of lattice points in that open disk, minus the collinear points where $u = v$ . The collinear condition gives

2u^2 < \frac{r^2}{32} \iff |u| < \frac{r}{8},

so the number of excluded points is

\frac{r}{4} - 1.

Final Formula

If circle_count denotes the number of lattice points satisfying

u^2 + v^2 < \frac{r^2}{32},

then

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}.

Editorial

The clean split is by the vertex at which the obtuse angle occurs. Dot products turn the conditions at $O$ and $C$ into simple linear inequalities inside the diamond $|x| + |y| \leq r$ , and the condition at $B$ turns into an open disk after completing the square.

Because those three regions are disjoint, the total count is the sum of their contributions. The first two are closed-form counts, while the third becomes a lattice-point count in a translated circle. After subtracting the collinear points on $y = x$ , the remaining computation is a single integer sweep over the horizontal offsets of that disk.

Pseudocode

Set r = 10^9.
region_OC = r^2 + r^2 / 2

s = r / 8
R2 = 2 * s^2
circle_count = 0

For each integer u from -floor(sqrt(R2 - 1)) to floor(sqrt(R2 - 1)):
    rem = R2 - u^2
    max_v = largest integer v with v^2 < rem
    Add 2 * max_v + 1 to circle_count

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

Return region_OC + region_B

Complexity Analysis

Time: $O(r/8)$ for the disk lattice-point sweep.
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
    long long region_OC = r * r + 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);

    long long 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
    long long collinear = r / 4 - 1;
    long long region_B = circle_count - collinear;
    long long answer = region_OC + region_B;

    cout << answer << 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))