Problem 184: Triangles Containing the Origin

Mathematical Foundation

Theorem 1. A non-degenerate triangle with vertices $A, B, C$ (none at the origin) strictly contains the origin if and only if the three vertices, viewed from the origin, do not all lie in any closed half-plane bounded by a line through the origin.

Proof. A point $O$ lies strictly inside triangle $ABC$ if and only if $O$ is on the same (strict) side of each of the three lines $AB$, $BC$, $CA$. Equivalently, viewing $A, B, C$ as vectors from $O$, the angles $\angle AOB$, $\angle BOC$, $\angle COA$ (measured as arcs going around) each satisfy the condition that no semicircle contains all three points. If all three points lay in a closed half-plane, the origin would be on or outside the corresponding edge, a contradiction. Conversely, if no half-plane contains all three, the origin must be interior. $\square$

Theorem 2 (Complementary Counting). Let $N$ be the number of non-origin lattice points with $x^2 + y^2 \leq R^2$. The number of triangles containing the origin equals

where $c_i$ is the number of points with angle strictly in $(\theta_i, \theta_i + \pi)$ (i.e., in the open semicircle starting just after point $i$).

Proof. A triple of non-origin points fails to contain the origin if and only if all three lie in some closed semicircle. We sort all $N$ points by their angle $\theta_i = \mathrm{atan2}(y_i, x_i)$. For a “bad” triple $\{P_a, P_b, P_c\}$ lying in a semicircle, define the “first” point as the one such that proceeding counterclockwise from it, all three points fit within an arc of length $\leq \pi$. For each point $P_i$, the points in the open semicircle $(\theta_i, \theta_i + \pi)$ are the candidates for the other two members of a bad triple where $P_i$ is first. Thus the number of bad triples is $\sum_i \binom{c_i}{2}$. Each bad triple is counted exactly once (by its unique “first” point in the angular sweep). $\square$

Lemma 1. For a circle of radius $R = 105$, the number of lattice points on or inside the circle (excluding the origin) is $N = \#\{(x,y) \in \mathbb{Z}^2 : 0 < x^2 + y^2 \leq R^2\}$. The two-pointer method computes all $c_i$ values in $O(N)$ time after $O(N \log N)$ sorting.

Proof. After sorting angles, we maintain a pointer $j$ for each $i$ marking the farthest point within the semicircle. As $i$ advances, $j$ can only advance (the semicircle window slides). Thus the total pointer movement is $O(N)$. $\square$

Editorial

Count triangles with integer-coordinate vertices on/inside circle of radius 105 that strictly contain the origin. Method: complementary counting with angular sweep. We collect non-origin lattice points. We then sort by angle. Finally, two-pointer sweep for semicircle counts.

Pseudocode

Collect non-origin lattice points
Sort by angle
Two-pointer sweep for semicircle counts

Complexity Analysis

• Time: $O(N \log N)$ for sorting, plus $O(N)$ for the two-pointer sweep, where $N \approx \pi \cdot 105^2 \approx 34{,}636$ lattice points.
• Space: $O(N)$ for storing points and angles.

Answer

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

int main(){
    const int R = 105;
    const long long R2 = (long long)R * R;

    // Collect non-origin lattice points inside/on circle
    // We'll sort by angle using cross/dot product comparisons to avoid floating point

    // Group points by direction (reduced direction vector)
    // For the semicircle counting, we use a standard approach:
    // Sort by angle, then two-pointer

    struct Point {
        int x, y;
    };

    vector<Point> pts;
    for(int x = -R; x <= R; x++){
        for(int y = -R; y <= R; y++){
            if(x == 0 && y == 0) continue;
            if((long long)x*x + (long long)y*y <= R2){
                pts.push_back({x, y});
            }
        }
    }

    int N = pts.size();

    // Sort by angle using atan2 (careful with precision)
    // Use a comparator based on half-plane then cross product
    auto half = [](const Point& p) -> int {
        // 0 for upper half-plane (y > 0, or y == 0 && x > 0)
        // 1 for lower half-plane
        if(p.y != 0) return (p.y > 0) ? 0 : 1;
        return (p.x > 0) ? 0 : 1;
    };

    sort(pts.begin(), pts.end(), [&](const Point& a, const Point& b){
        int ha = half(a), hb = half(b);
        if(ha != hb) return ha < hb;
        long long cross = (long long)a.x * b.y - (long long)a.y * b.x;
        return cross > 0; // a before b if cross > 0 (a is counterclockwise before b)
    });

    // Two-pointer: for each point i, count points strictly in (angle_i, angle_i + pi)
    // A point j is in the open semicircle (angle_i, angle_i + pi) if:
    //   cross(i, j) > 0 (j is strictly counterclockwise from i)
    //   AND dot-check that j is not past pi from i
    // Actually: j is in (theta_i, theta_i + pi) iff
    //   cross(i, j) > 0  (strictly counterclockwise, less than pi away)

    // Duplicate the array for wraparound
    vector<Point> ext(2 * N);
    for(int i = 0; i < N; i++){
        ext[i] = pts[i];
        ext[i + N] = pts[i]; // wrapped
    }

    // cross(a, b) > 0 means b is strictly CCW from a (angle between 0 and pi)
    // cross(a, b) = 0 means collinear
    // cross(a, b) < 0 means b is CW or past pi

    // For point i, we want j such that cross(pts[i], pts[j % N]) > 0
    // This means pts[j] is in the open semicircle (theta_i, theta_i + pi)

    long long bad = 0;
    int j = 0;
    for(int i = 0; i < N; i++){
        if(j <= i) j = i + 1;
        // Advance j while cross(pts[i], ext[j]) > 0
        while(j < i + N){
            long long cross = (long long)pts[i].x * ext[j].y - (long long)pts[i].y * ext[j].x;
            if(cross <= 0) break;
            j++;
        }
        long long cnt = j - i - 1;
        bad += cnt * (cnt - 1) / 2;
    }

    long long total = (long long)N * (N - 1) * (N - 2) / 6;
    cout << total - bad << endl;

    return 0;
}

"""
Problem 184: Triangles Containing the Origin

Count triangles with integer-coordinate vertices on/inside circle of radius 105
that strictly contain the origin.

Method: complementary counting with angular sweep.
"""

def solve():
    R = 105
    R2 = R * R

    # Collect non-origin lattice points
    pts = []
    for x in range(-R, R + 1):
        for y in range(-R, R + 1):
            if x == 0 and y == 0:
                continue
            if x * x + y * y <= R2:
                pts.append((x, y))

    N = len(pts)

    # Sort by angle using half-plane + cross product
    def sort_key(p):
        x, y = p
        # half: 0 for upper (y>0 or y==0,x>0), 1 for lower
        if y != 0:
            h = 0 if y > 0 else 1
        else:
            h = 0 if x > 0 else 1
        return h

    # Custom sort
    from functools import cmp_to_key

    def cmp(a, b):
        ha = 0 if (a[1] > 0 or (a[1] == 0 and a[0] > 0)) else 1
        hb = 0 if (b[1] > 0 or (b[1] == 0 and b[0] > 0)) else 1
        if ha != hb:
            return -1 if ha < hb else 1
        cross = a[0] * b[1] - a[1] * b[0]
        if cross > 0:
            return -1
        elif cross < 0:
            return 1
        return 0

    pts.sort(key=cmp_to_key(cmp))

    # Two-pointer sweep
    bad = 0
    j = 0
    for i in range(N):
        if j <= i:
            j = i + 1
        while j < i + N:
            jj = j % N
            cross = pts[i][0] * pts[jj][1] - pts[i][1] * pts[jj][0]
            if cross <= 0:
                break
            j += 1
        cnt = j - i - 1
        bad += cnt * (cnt - 1) // 2

    total = N * (N - 1) * (N - 2) // 6
    print(total - bad)

if __name__ == "__main__":
    solve()