Detailed mathematical approach

Problem Summary

Each input row gives one triangle \(ABC\) by listing three integer vertices. The task is to count how many of those triangles contain the origin \(O=(0,0)\) in their interior. Because the tested point never changes, this is not a general point-in-polygon problem; the geometry collapses to a small orientation test involving three signed areas.

Mathematical Approach

Let \(A=(x_1,y_1)\), \(B=(x_2,y_2)\), and \(C=(x_3,y_3)\). The implementations do not use floating-point angles, explicit line intersections, or any iterative search. They evaluate three determinants formed with the origin:

$s_1=x_1y_2-y_1x_2,\qquad s_2=x_2y_3-y_2x_3,\qquad s_3=x_3y_1-y_3x_1.$

Geometrically, \(s_1\), \(s_2\), and \(s_3\) are twice the signed areas of the triangles \(OAB\), \(OBC\), and \(OCA\). Their signs tell us whether each consecutive pair of vertex vectors turns counterclockwise or clockwise around the origin.

The Signed-Area Identity

The whole triangle also has a signed area, namely

$\Delta=\det(B-A,C-A)=x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2).$

Expanding this determinant gives the key identity

$\Delta=s_1+s_2+s_3.$

So the three subareas cut out by the origin add up to the oriented area of \(ABC\). This is the invariant behind the containment test: the origin is inside exactly when those subareas fit together with a consistent orientation.

Barycentric Coordinates of the Origin

A point lies strictly inside a triangle exactly when its barycentric coordinates are all positive. For the origin, the representation

$O=\lambda_1A+\lambda_2B+\lambda_3C,\qquad \lambda_1+\lambda_2+\lambda_3=1$

has the especially simple closed form

$\lambda_1=\frac{s_2}{\Delta},\qquad \lambda_2=\frac{s_3}{\Delta},\qquad \lambda_3=\frac{s_1}{\Delta}.$

Therefore \(O\) is strictly inside \(ABC\) if and only if all three ratios are positive. Since the denominator is common, this happens precisely when \(s_1\), \(s_2\), and \(s_3\) all have the same nonzero sign.

Why the Determinant Test Is Enough

A triangle is convex, so one negative barycentric coordinate already proves that the point lies outside the edge opposite the corresponding vertex. In determinant language, if one of \(s_1,s_2,s_3\) has the opposite sign from the other two, the origin is outside. If one determinant is zero, then \(O\) is collinear with one side, so the origin lies on the boundary rather than in the strict interior.

That is why the decisive condition is simply

$s_1,s_2,s_3 \gt 0\quad\text{or}\quad s_1,s_2,s_3 \lt 0.$

No divisions are needed in the implementation, and integer arithmetic keeps the test exact.

Worked Example

Consider the triangle

$A=(-340,495),\qquad B=(-153,-910),\qquad C=(835,-947).$

Then

$s_1=385135,\qquad s_2=904741,\qquad s_3=91345.$

All three values are positive, so all three barycentric coordinates of the origin are positive as well. Hence the origin lies inside this triangle.

For comparison, with

$A=(-175,41),\qquad B=(-421,-714),\qquad C=(574,-645)$

we get

$s_1=142211,\qquad s_2=681381,\qquad s_3=-89341.$

The signs are mixed, so one barycentric coordinate is negative and the origin lies outside.

How the Code Works

The C++, Python, and Java implementations all scan the triangle list row by row, split each row into six integers, and interpret them as the coordinates of \(A\), \(B\), and \(C\). For each triangle they compute the three determinants \(s_1\), \(s_2\), and \(s_3\) above. There is no preprocessing phase because every triangle can be decided independently.

The final decision is a sign check. The C++ implementation uses the strict form "all three positive or all three negative," which matches strict containment exactly. The Python and Java implementations encode the equivalent "no mixed signs" rule; away from the boundary case \(s_i=0\), it gives the same answer. Every triangle that passes the test increments a running counter, and that counter is the final output.

Complexity Analysis

If there are \(N\) triangles, the algorithm performs a constant amount of work per triangle: three 2-by-2 determinants and a few sign comparisons. The total running time is therefore \(O(N)\).

The geometric test itself uses \(O(1)\) extra space. Some implementations may store input lines before processing them, but the mathematical core needs only the current triangle and the running count. For the Project Euler input size, the computation is effectively instantaneous.

Footnotes and References

1. Problem page: Project Euler 102
2. Cross product and planar orientation: Wikipedia - Cross product
3. Barycentric coordinates: Wikipedia - Barycentric coordinate system
4. Coordinate formulas for triangle area: Wikipedia - Area of a triangle
5. Containment tests based on orientation: Wikipedia - Point in polygon