Project Euler

Integer Angled Quadrilaterals

Let ABCD be a convex quadrilateral with diagonals AC and BD. At each vertex, the diagonal makes an angle with each of the two sides, creating eight corner angles. How many non-similar convex quadri...

Source sync Apr 19, 2026

Problem #0177

Level Level 12

Solved By 1,554

Languages C++, Python

Answer 129325

Length 483 words

geometrygraphbrute_force

Let $ABCD$ be a convex quadrilateral, with diagonals $AC$ and $BD$. At each vertex the diagonal makes an angle with each of the two sides, creating eight corner angles.

Problem illustration

For example, at vertex $A$, the two angles are $CAD$, $CAB$.

We call such a quadrilateral for which all eight corner angles have integer values when measured in degrees an "integer angled quadrilateral". An example of an integer angled quadrilateral is a square, where all eight corner angles are $45^\circ$. Another example is given by $DAC = 20^\circ$, $BAC = 60^\circ$, $ABD = 50^\circ$, $CBD = 30^\circ$, $BCA = 40^\circ$, $DCA = 30^\circ$, $CDB = 80^\circ$, $ADB = 50^\circ$.

What is the total number of non-similar integer angled quadrilaterals?

Note: In your calculations you may assume that a calculated angle is integral if it is within a tolerance of $10^{-9}$ of an integer value.

Problem 177: Integer Angled Quadrilaterals

Mathematical Analysis

Setup

The two diagonals AC and BD intersect at point P inside the convex quadrilateral, creating four triangles. Label the eight sub-angles:

At A: $\alpha$ (toward B) and $\beta$ (toward D), split by diagonal AC
At B: $\gamma$ (toward A) and $\delta$ (toward C), split by diagonal BD
At C: $\varepsilon$ (toward B) and $\zeta$ (toward D), split by diagonal AC
At D: $\eta$ (toward C) and $\theta$ (toward A), split by diagonal BD

Constraints from Triangle Angle Sums

Let $p$ be the angle at the intersection point P in triangle APB. Then from the four sub-triangles:

\alpha + \gamma = 180 - p, \quad \delta + \varepsilon = p, \quad \zeta + \eta = 180 - p, \quad \theta + \beta = p

Geometric Closure Condition

For the quadrilateral to close (the two diagonals to intersect consistently), the sine rule in each sub-triangle yields the crucial constraint:

\sin(\alpha)\sin(\delta)\sin(\zeta)\sin(\theta) = \sin(\beta)\sin(\gamma)\sin(\varepsilon)\sin(\eta)

This is derived from the requirement that the four segments AP, BP, CP, DP have consistent lengths across all four sub-triangles.

Free Variables

Given $p$ , the 8 angles are determined by 4 free variables: $\alpha, \delta, \zeta, \theta$ (with $\gamma, \varepsilon, \eta, \beta$ derived). The closure condition reduces this to 3 effective degrees of freedom. For computation, we fix $\alpha, \delta, \zeta$ and solve for $\theta$ :

\tan(\theta) = \frac{R \cdot \sin(p)}{L + R \cdot \cos(p)}

where $L = \sin(\alpha)\sin(\delta)\sin(\zeta)$ and $R = \sin(\gamma)\sin(\varepsilon)\sin(\eta)$ .

Ranges

$p$ : 2 to 178
$\alpha, \zeta$ : 1 to $179 - p$ (so that $\gamma, \eta \geq 1$ )
$\delta$ : 1 to $p - 1$ (so that $\varepsilon \geq 1$ )
$\theta$ : solved from closure, must be integer in $[1, p-1]$

Convexity

The quadrilateral angles $A = \alpha + \beta$ , $B = \gamma + \delta$ , $C = \varepsilon + \zeta$ , $D = \eta + \theta$ must all be less than 180.

Symmetry Reduction

The dihedral group of order 8 acts on the quadrilateral via vertex relabelings. The generators are:

Rotation $r$ : ABCD $\to$ BCDA maps

(\alpha,\beta,\gamma,\delta,\varepsilon,\zeta,\eta,\theta) \to (\delta,\gamma,\varepsilon,\zeta,\eta,\theta,\beta,\alpha)

Reflection $s$ : ABCD $\to$ ADCB maps

(\alpha,\beta,\gamma,\delta,\varepsilon,\zeta,\eta,\theta) \to (\beta,\alpha,\theta,\eta,\zeta,\varepsilon,\delta,\gamma)

These generate 8 symmetries. Two 8-tuples in the same orbit represent similar quadrilaterals. We canonicalize each valid tuple under this group and count distinct canonical forms.

Editorial

Count non-similar convex quadrilaterals ABCD where both diagonals split all four angles into integer-degree sub-angles. 8 sub-angles: alpha=BAC, beta=CAD, gamma=ABD, delta=DBC, epsilon=BCA, zeta=ACD, eta=CDB, theta=BDA Constraints from diagonal intersection angle p: alpha+gamma = 180-p, delta+epsilon = p, zeta+eta = 180-p, theta+beta = p Closure: sin(alpha)*sin(delta)*sin(zeta)*sin(theta) = sin(beta)*sin(gamma)*sin(epsilon)*sin(eta) Symmetry group (dihedral-8) reduces count by factor ~8. We iterate over each $p$ from 2 to 178. We then iterate over each $(\alpha, \delta, \zeta)$ in valid ranges. Finally, solve for $\theta$ using the closure condition.

Pseudocode

For each $p$ from 2 to 178:
For each $(\alpha, \delta, \zeta)$ in valid ranges:
Solve for $\theta$ using the closure condition
If $\theta$ is a positive integer in range, verify the closure and convexity
Canonicalize the 8-tuple under the dihedral-8 symmetry group
Insert into a set of canonical forms
Output the size of the set

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$

Answer

\boxed{129325}

Complexity

The outer loops iterate $O(178 \times 178 \times 178 \times 178) \approx 10^9$ in the worst case, but the average is much smaller (about $1.25 \times 10^8$ due to range constraints). The atan2-based solver and canonicalization add $O(1)$ per iteration. Total runtime is a few seconds.

C++ project_euler/problem_177/solution.cpp

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

// Problem 177: Integer Angled Quadrilaterals
// Fixed range: alpha and zeta can go up to 179-p (not 178-p).
// Convexity requires A,B,C,D < 180, not the sub-angle pair sums.

int main() {
    double sinv[181];
    for (int i = 0; i <= 180; i++) sinv[i] = sin(i * M_PI / 180.0);

    typedef array<int,8> T8;

    int r_perm[8] = {3,2,4,5,6,7,1,0};
    int s_perm[8] = {1,0,7,6,5,4,3,2};

    int perms[8][8];
    for (int i = 0; i < 8; i++) perms[0][i] = i;
    for (int i = 0; i < 8; i++) perms[1][i] = r_perm[i];
    for (int k = 2; k <= 3; k++)
        for (int i = 0; i < 8; i++) perms[k][i] = perms[k-1][r_perm[i]];
    for (int i = 0; i < 8; i++) perms[4][i] = s_perm[i];
    for (int k = 5; k <= 7; k++)
        for (int i = 0; i < 8; i++) perms[k][i] = perms[4][perms[k-4][i]];

    auto canonical = [&](const T8& t) -> T8 {
        T8 best = t;
        for (int sym = 1; sym < 8; sym++) {
            T8 tt;
            for (int i = 0; i < 8; i++) tt[i] = t[perms[sym][i]];
            if (tt < best) best = tt;
        }
        return best;
    };

    set<T8> seen;

    for (int p = 2; p <= 178; p++) {
        double sp = sinv[p], cp = cos(p * M_PI / 180.0);
        int max_az = 179 - p;  // FIXED: was 178-p
        int max_d = p - 1;

        for (int alpha = 1; alpha <= max_az; alpha++) {
            int gamma = 180 - p - alpha;
            for (int delta = 1; delta <= max_d; delta++) {
                int epsilon = p - delta;
                for (int zeta = 1; zeta <= max_az; zeta++) {
                    int eta = 180 - p - zeta;

                    double L = sinv[alpha] * sinv[delta] * sinv[zeta];
                    double R = sinv[gamma] * sinv[epsilon] * sinv[eta];

                    double y = R * sp;
                    double x = L + R * cp;
                    double theta_exact = atan2(y, x) * 180.0 / M_PI;

                    if (theta_exact < 0.5 || theta_exact > max_d + 0.5) continue;

                    int t_round = (int)round(theta_exact);
                    for (int theta = max(1, t_round - 1); theta <= min(max_d, t_round + 1); theta++) {
                        int beta = p - theta;
                        if (beta < 1) continue;

                        double lhs = sinv[alpha] * sinv[delta] * sinv[zeta] * sinv[theta];
                        double rhs = sinv[beta] * sinv[gamma] * sinv[epsilon] * sinv[eta];
                        double rel = fabs(lhs - rhs) / max(fabs(lhs), fabs(rhs));
                        if (rel > 1e-9) continue;

                        // Convexity: quad angles < 180
                        int A = alpha + beta, B = gamma + delta, C = epsilon + zeta, D = eta + theta;
                        if (A >= 180 || B >= 180 || C >= 180 || D >= 180) continue;

                        T8 t = {alpha, beta, gamma, delta, epsilon, zeta, eta, theta};
                        seen.insert(canonical(t));
                    }
                }
            }
        }
    }

    cout << seen.size() << endl;
    return 0;
}

Python project_euler/problem_177/solution.py

"""
Problem 177: Integer Angled Quadrilaterals

Count non-similar convex quadrilaterals ABCD where both diagonals split
all four angles into integer-degree sub-angles.

8 sub-angles: alpha=BAC, beta=CAD, gamma=ABD, delta=DBC,
              epsilon=BCA, zeta=ACD, eta=CDB, theta=BDA

Constraints from diagonal intersection angle p:
  alpha+gamma = 180-p, delta+epsilon = p, zeta+eta = 180-p, theta+beta = p

Closure: sin(alpha)*sin(delta)*sin(zeta)*sin(theta) = sin(beta)*sin(gamma)*sin(epsilon)*sin(eta)

Symmetry group (dihedral-8) reduces count by factor ~8.
"""

import math

sinv = [0.0] * 181
for i in range(181):
    sinv[i] = math.sin(i * math.pi / 180.0)

# Permutations for dihedral-8 symmetry group
# r: rotation ABCD->BCDA
# s: reflection ABCD->ADCB
r_perm = [3, 2, 4, 5, 6, 7, 1, 0]
s_perm = [1, 0, 7, 6, 5, 4, 3, 2]

perms = [None] * 8
perms[0] = list(range(8))
perms[1] = r_perm[:]
for k in range(2, 4):
    perms[k] = [perms[k-1][r_perm[i]] for i in range(8)]
perms[4] = s_perm[:]
for k in range(5, 8):
    perms[k] = [perms[4][perms[k-4][i]] for i in range(8)]

def canonical(t):
    best = t
    for s in range(1, 8):
        tt = tuple(t[perms[s][i]] for i in range(8))
        if tt < best:
            best = tt
    return best

seen = set()

for p in range(2, 179):
    sp = sinv[p]
    cp = math.cos(p * math.pi / 180.0)
    max_az = 179 - p
    max_d = p - 1

    for alpha in range(1, max_az + 1):
        gamma = 180 - p - alpha
        for delta in range(1, max_d + 1):
            epsilon = p - delta
            for zeta in range(1, max_az + 1):
                eta = 180 - p - zeta

                L = sinv[alpha] * sinv[delta] * sinv[zeta]
                R = sinv[gamma] * sinv[epsilon] * sinv[eta]

                y = R * sp
                x = L + R * cp
                theta_exact = math.atan2(y, x) * 180.0 / math.pi

                if theta_exact < 0.5 or theta_exact > max_d + 0.5:
                    continue

                t_round = round(theta_exact)
                for theta in range(max(1, t_round - 1), min(max_d, t_round + 1) + 1):
                    beta = p - theta
                    if beta < 1:
                        continue

                    lhs = sinv[alpha] * sinv[delta] * sinv[zeta] * sinv[theta]
                    rhs = sinv[beta] * sinv[gamma] * sinv[epsilon] * sinv[eta]
                    mx = max(abs(lhs), abs(rhs))
                    if mx == 0:
                        continue
                    if abs(lhs - rhs) / mx > 1e-9:
                        continue

                    A = alpha + beta
                    B = gamma + delta
                    C = epsilon + zeta
                    D = eta + theta
                    if A >= 180 or B >= 180 or C >= 180 or D >= 180:
                        continue

                    t = (alpha, beta, gamma, delta, epsilon, zeta, eta, theta)
                    seen.add(canonical(t))

print(len(seen))