Detailed mathematical approach

Problem Summary

Let

$P_r=\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}:x^2+y^2\lt r^2\}.$

For the actual Project Euler input, \(r=105\). The task is to count unordered triangles whose three vertices are chosen from \(P_{105}\) and whose interior contains the origin strictly, not merely on an edge or on a degenerate line.

A direct approach would examine all \(\binom{N}{3}\) triples of lattice points and run a point-in-triangle test on each one, where \(N=|P_r|\). The implementations avoid that completely. They reorganize the point set by polar angle, group points that lie on the same ray from the origin, and then subtract the triples that are geometrically impossible instead of testing triangles one by one.

Mathematical Approach

From Triangles to Angular Intervals

A nondegenerate triangle contains the origin if and only if the origin lies in the convex hull of its three vertices. Equivalently, a triangle misses the origin if there exists a line through the origin such that all three vertices lie in one closed half-plane determined by that line. In angular language, that means the three vertex directions fit inside some closed interval of length \(\pi\).

So the problem is easier to solve in complementary form: count all triples of lattice points, then subtract every triple whose three directions can be packed into a closed semicircle, together with the collinear cases where the “triangle” has zero area.

Rays, Primitive Directions, and Multiplicities

When two lattice points have the same polar angle, they lie on the same ray from the origin. If \((u,v)\) is a primitive lattice direction with \(\gcd(u,v)=1\), then the points on that ray are

$ (u,v),\ 2(u,v),\ 3(u,v),\dots $

up to the largest multiple still satisfying \(k^2(u^2+v^2)\lt r^2\). Let \(c\) denote the number of such points on one ray. The opposite ray \((-u,-v)\) has the same multiplicity \(c\), so each unoriented line through the origin contributes \(2c\) lattice points altogether.

Now let \(N=|P_r|\). By central symmetry, every point is paired with its opposite, so \(N\) is even. Write

$H=\frac{N}{2}.$

For a fixed line through the origin with multiplicity \(c\) on each ray, removing the \(2c\) points on the line leaves \(N-2c\) points off the line, split evenly between the two open half-planes. Therefore each open side contains exactly \(H-c\) points.

The Four Bad Configurations for One Line Through the Origin

Fix one such line and classify every triple that fails the strict containment condition because of this line. The bad triples are mutually exclusive and fall into four natural types.

1. One boundary vertex, two interior vertices on the same side. Choose one vertex on either ray of the line, then choose two vertices from the open half-plane on that same side. This gives

$2c\binom{H-c}{2}=c(H-c)(H-c-1).$

The factor \(2\) reflects the fact that either of the two opposite rays can supply the boundary vertex of the minimal closed semicircle.

2. Two vertices on the same ray, third vertex on that same side. If two chosen points lie on one ray and the third lies strictly in the adjacent open half-plane, the origin cannot lie inside the triangle. Counting both rays gives

$2\binom{c}{2}(H-c)=c(c-1)(H-c).$

3. One vertex on each opposite ray. Then the segment joining those two vertices passes through the origin, so the origin lies on an edge rather than in the interior. The third vertex can be any point not on the same line, hence

$c^2(N-2c).$

4. All three vertices on the same line through the origin. These choices are degenerate and contribute

$\binom{2c}{3}.$

Summing these four contributions over all unoriented lines through the origin counts every triple that does not produce a valid “origin-containing” triangle exactly once.

Worked Example: \(r=2\)

For \(r=2\), the nonzero interior lattice points are the four axis points and the four diagonal points, so \(N=8\) and \(H=4\). There are four relevant lines through the origin, and each one has \(c=1\) point on each ray.

For one line the bad contribution is

$1\cdot(4-1)(4-2)+1^2(8-2)+1\cdot 0\cdot(4-1)+\binom{2}{3}=6+6+0+0=12.$

All four lines behave the same way, so the total number of bad triples is \(4\cdot 12=48\). Since

$\binom{8}{3}=56,$

the number of triangles containing the origin is

$56-48=8,$

which matches the checkpoint used by the implementations.

Closed Formula

If the equal-angle groups from one half-turn have multiplicities \(c_1,c_2,\dots,c_m\), then each \(c_j\) represents one unoriented line through the origin, and the final answer is

$\boxed{\binom{N}{3}-\sum_{j=1}^{m}\left(c_j(H-c_j)(H-c_j-1)+c_j^2(N-2c_j)+c_j(c_j-1)(H-c_j)+\binom{2c_j}{3}\right).}$

This is the exact mathematics implemented by the C++, Python, and Java solutions. The source code simply writes the middle two contributions as one combined subtraction.

How the Code Works

The C++, Python, and Java implementations enumerate every integer point in the square \([-r,r]\times[-r,r]\), discard the origin and every point on or outside the circle, and compute the polar angle \(\operatorname{atan2}(y,x)\) for each surviving point. After sorting those angles, equal-angle runs correspond precisely to points that share one ray from the origin.

Because every lattice point has the opposite point \((-x,-y)\), the sorted angle list naturally breaks into opposite pairs separated by \(\pi\). That is why the implementations only scan one half of the sorted list: this visits each line through the origin exactly once. During that scan, a small tolerance is used to merge angles that should be identical mathematically.

The running total starts at \(\binom{N}{3}\). For each equal-angle run of size \(c\), the implementation evaluates the three subtraction statements visible in the code: the “one boundary vertex” term, the combined “two on a ray or one on each opposite ray” term, and the fully collinear term \(\binom{2c}{3}\). After every representative line has been processed, the remaining total is exactly the number of triangles that contain the origin strictly inside.

Complexity Analysis

The grid scan checks \((2r+1)^2\) candidate lattice points, so the enumeration phase costs \(O(r^2)\). If \(N=|P_r|\), then \(N=\Theta(r^2)\), and sorting the angle list costs \(O(N\log N)\).

The final grouping pass is linear, \(O(N)\), and memory usage is \(O(N)\) for the stored angles. For the actual value \(r=105\), this is comfortably fast because the method never performs an explicit \(O(N^3)\) triangle test.

Footnotes and References

1. Problem page: Project Euler 184
2. Polar coordinates: Wikipedia - Polar coordinate system
3. Half-plane: Wikipedia - Half-plane
4. Barycentric coordinates: Wikipedia - Barycentric coordinate system
5. Lattice points in circles: Wikipedia - Gauss circle problem