EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
All Euler problems
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 May 21, 2026
Problem #0177
Level Level 12
Solved By 1,554
Languages C++, Python
Answer 129325
Length 488 words
geometrygraphbrute_force
Problem statement

Problem Statement

This archive keeps the full statement, math, and original media on the page.

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 content is attributed to Project Euler and included here under the CC BY-NC-SA 4.0 license.

Open official problem License details

Problem 177: Integer Angled Quadrilaterals

Mathematical Development

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 pp be the angle at the intersection point P in triangle APB. Then from the four sub-triangles:

α+γ=180−p,δ+ε=p,ζ+η=180−p,θ+β=p\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⁡(α)sin⁡(δ)sin⁡(ζ)sin⁡(θ)=sin⁡(β)sin⁡(γ)sin⁡(ε)sin⁡(η)\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 pp, 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⁡(θ)=R⋅sin⁡(p)L+R⋅cos⁡(p)\tan(\theta) = \frac{R \cdot \sin(p)}{L + R \cdot \cos(p)}

where L=sin⁡(α)sin⁡(δ)sin⁡(ζ)L = \sin(\alpha)\sin(\delta)\sin(\zeta) and R=sin⁡(γ)sin⁡(ε)sin⁡(η)R = \sin(\gamma)\sin(\varepsilon)\sin(\eta).

Ranges

  • pp: 2 to 178
  • α,ζ\alpha, \zeta: 1 to 179−p179 - p (so that γ,η≥1\gamma, \eta \geq 1)
  • δ\delta: 1 to p−1p - 1 (so that ε≥1\varepsilon \geq 1)
  • θ\theta: solved from closure, must be integer in [1,p−1][1, p-1]

Convexity

The quadrilateral angles A=α+βA = \alpha + \beta, B=γ+δB = \gamma + \delta, C=ε+ζC = \varepsilon + \zeta, D=η+θ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 rr: ABCD →\to BCDA maps

(α,β,γ,δ,ε,ζ,η,θ)→(δ,γ,ε,ζ,η,θ,β,α)(\alpha,\beta,\gamma,\delta,\varepsilon,\zeta,\eta,\theta) \to (\delta,\gamma,\varepsilon,\zeta,\eta,\theta,\beta,\alpha)

Reflection ss: 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

The implementation treats the intersection angle pp and three of the corner sub-angles as free variables. Once pp, α\alpha, δ\delta, and ζ\zeta are chosen, the companion angles γ\gamma, ε\varepsilon, and η\eta are forced by the triangle-sum identities, and the closure equation determines the only plausible value of θ\theta. Instead of blindly trying every integer θ\theta, the code uses the trigonometric identity to compute a floating-point estimate with atan2, then tests only the nearby integer candidates.

That leaves two final filters. The sine-product equation must still hold to high precision, and the resulting quadrilateral angles must all stay below 180 degrees to ensure convexity. Every surviving 8-tuple is then canonicalized under the dihedral symmetry group of the quadrilateral, so all rotated or reflected copies collapse to a single representative before counting.

Pseudocode

Precompute the sine values for all integer angles from 0 to 180 degrees.
Prepare the eight symmetry permutations of the quadrilateral labels.

For each intersection angle $p$ from 2 to 178:
    For each admissible triple $(\alpha, \delta, \zeta)$:
        derive $\gamma$, $\varepsilon$, and $\eta$ from the angle-sum constraints.

        Use the closure equation to estimate $\theta$ with `atan2`.
        Check only the small set of nearby integer values of $\theta`.

        For each such candidate:
            derive $\beta = p - \theta$.
            verify the sine-product closure condition numerically.
            verify that all four full quadrilateral angles are strictly below 180.

            Form the 8-tuple of sub-angles.
            Replace it by the lexicographically smallest image under the dihedral symmetries.
            Insert that canonical tuple into a set.

Return the size of the set.

Complexity Analysis

The outer loops cover all admissible values of pp, α\alpha, δ\delta, and ζ\zeta, but the angle constraints shrink the practical search far below the naive quartic bound. For each surviving triple, solving for θ\theta, checking closure, and canonicalizing under the eight symmetries all take constant time. The total runtime is therefore dominated by the nested enumeration and is practical in a few seconds.

Answer

129325\boxed{129325}
Source code

Code

Each problem page includes the exact C++ and Python source files from the local archive.

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