Problem 102: Triangle Containment

Project Euler Problem 102 Solution

EulerSolve provides an optimized solution for Project Euler Problem 102, Triangle Containment, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

Three distinct points with coordinates $-1000\le x,y\le1000$ are chosen at random so that they form a triangle. The file triangles.txt holds one thousand such "random" triangles, one per line, each written as six whole numbers separated by commas: the coordinates $x_1,y_1,x_2,y_2,x_3,y_3$ of its three corners. We must count the triangles whose interior contains the origin $O=(0,0)$. The statement gives two examples, which are also the first two lines of the file: the triangle with corners $A=(-340,495)$, $B=(-153,-910)$ and $C=(835,-947)$ contains the origin, and the triangle with corners $X=(-175,41)$, $Y=(-421,-714)$ and $Z=(574,-645)$ does not. ^[1] An origin lying on a side would not count; Section 7 shows that the file has no such case.

The whole solution in one sentence: if we walk around a triangle from corner to corner, the origin is inside exactly when it stays on the same side of us all the way round, always on our left or always on our right, and for each side one cross product of whole numbers tells us which side that is, with no rounding at all.

Mathematical Approach

We start with two tiny triangles, turn their lesson into arithmetic and prove it; then we treat the boundary, other tests, and how often a random triangle contains the origin.

1. Two tiny triangles

Take the triangle $T_1$ with corners $A=(-1,-1)$, $B=(2,-1)$ and $C=(0,2)$, which contains the origin. Walk around it, from $A$ to $B$, on to $C$ and back to $A$. On the first side we walk to the right, and the origin, which lies above us, is on our left; on the other two sides it is on our left as well. The triangle $T_2$ with corners $(1,1)$, $(3,1)$ and $(1,3)$ does not contain the origin. Walking from $(1,1)$ to $(3,1)$ we have the origin on our right, but on the side from $(3,1)$ to $(1,3)$ it is on our left. This is the whole idea: the origin is inside exactly when it stays on the same side during the whole walk. A program needs an exact way to compute "left" and "right".

2. The cross product

For two points $P=(x_P,y_P)$ and $Q=(x_Q,y_Q)$, each also read as an arrow from the origin, the cross product is the number

$$P\times Q=x_P\,y_Q-y_P\,x_Q,$$

the determinant of the $2\times2$ table whose columns are $P$ and $Q$. For example $(1,0)\times(0,1)=1$, $(0,1)\times(1,0)=-1$, $(2,1)\times(1,3)=6-1=5$ and $(2,1)\times(4,2)=0$. Its absolute value is the area of the parallelogram with sides $P$ and $Q$, so half of it is the area of the triangle $OPQ$. Its sign is positive when $Q$ points less than half a turn anticlockwise from $P$, negative for a clockwise turn, and zero when $O$, $P$ and $Q$ lie on one line. ^[2] To see why, write $P=r(\cos\alpha,\sin\alpha)$ and $Q=\rho(\cos\beta,\sin\beta)$ with lengths $r,\rho$ and directions $\alpha,\beta$. Then

$$\begin{aligned}P\times Q&=r\rho\,(\cos\alpha\sin\beta-\sin\alpha\cos\beta)\\&=r\rho\,\sin(\beta-\alpha),\end{aligned}$$

where $r$ is the base and $\rho\,|\sin(\beta-\alpha)|$ the height of the parallelogram. The sign is that of $\sin(\beta-\alpha)$. Taking the anticlockwise turn $\beta-\alpha$ from $P$ to $Q$ between $0^\circ$ and $360^\circ$, the sine is positive strictly between $0^\circ$ and $180^\circ$, negative between $180^\circ$ and $360^\circ$, that is, for a clockwise turn, and $0$ at $0^\circ$ and $180^\circ$, when the arrows point the same or opposite ways. For $P=(2,1)$ and $Q=(1,3)$, $Q=P+(-1,2)$, where $(-1,2)$ is $P$ turned a quarter turn anticlockwise; so $Q$ is the diagonal of the square on $P$, points $45^\circ$ further and has length $\sqrt2\cdot\sqrt5=\sqrt{10}$, and indeed $\sqrt5\cdot\sqrt{10}\cdot\sin45^\circ=5$. Two rules follow straight from the formula: swapping the arrows changes the sign, $Q\times P=-(P\times Q)$, so that $P\times P=0$; and the product multiplies out like an ordinary product, $(P+R)\times Q=P\times Q+R\times Q$ and $(kP)\times Q=k\,(P\times Q)$.

3. Left or right of a side

Walking along a side from $P$ to $Q$, a point $R$ is on our left when the arrow from $P$ to $R$ points less than half a turn anticlockwise from the arrow from $P$ to $Q$. By Section 2, with $P$ in the role of the origin, this happens exactly when $(Q-P)\times(R-P)\gt0$; the point is on our right when this number is negative, and on the line through $P$ and $Q$ when it is $0$. For the origin, $R=O$, the two rules of Section 2 simplify the test:

$$\begin{aligned}(Q-P)\times(-P)&=-\,Q\times P+P\times P\\&=P\times Q.\end{aligned}$$

So the origin is on our left when we walk from $P$ to $Q$ exactly when $P\times Q\gt0$, and for a triangle $ABC$ we need only the three numbers

$$s_1=A\times B,\quad s_2=B\times C,\quad s_3=C\times A,$$

one for each side of the walk $A\to B\to C\to A$. For $T_1$ they are $s_1=(-1)(-1)-(-1)\cdot2=3$, $s_2=2\cdot2-(-1)\cdot0=4$ and $s_3=0\cdot(-1)-2\cdot(-1)=2$, all positive: the origin is always on our left. For $T_2$ they are $-2$, $8$ and $-2$: right, left, right.

4. The test and its proof

On the walk from $A$ to $B$, the inside of the triangle is the side where $C$ lies, and by Section 3 the corner $C$ is on our left exactly when $\Delta=(B-A)\times(C-A)$ is positive. Multiplying out with the rules of Section 2 gives

$$\begin{aligned}\Delta&=B\times C-B\times A-A\times C+A\times A\\&=s_1+s_2+s_3,\end{aligned}$$

and the walk from $B$ to $C$ with the corner $A$, and the walk from $C$ to $A$ with the corner $B$, give the same sum. So all three opposite corners lie on our left when $\Delta\gt0$ and on our right when $\Delta\lt0$. The number $\Delta$ is twice the signed area of the triangle, positive when the corners are listed anticlockwise, and the identity $\Delta=s_1+s_2+s_3$ is the shoelace formula for a triangle: the signed area of $ABC$ is the sum of the signed areas of $OAB$, $OBC$ and $OCA$. ^[3] For $T_1$, $\Delta=(3,0)\times(1,3)=9=3+4+2$.

The interior of a triangle consists of the points that lie, for each side, strictly on the same side of its line as the opposite corner. So for a genuine triangle, where $\Delta\ne0$, the origin is inside exactly when every $s_i$ has the sign of $\Delta$, and since three numbers of one sign give a sum of that sign, this proves the test: the origin is inside exactly when $s_1$, $s_2$, $s_3$ are all positive or all negative. The test needs neither $\Delta$ nor the direction in which the corners are listed, which matters: the file lists $478$ triangles anticlockwise and $522$ clockwise.

5. The origin as a weighted average of the corners

The same numbers tell us more. For any three points,

$$s_2\,A+s_3\,B+s_1\,C=(0,0).$$

With $A=(x_1,y_1)$, $B=(x_2,y_2)$, $C=(x_3,y_3)$, the first coordinate $(x_2y_3-y_2x_3)\,x_1$${}+(x_3y_1-y_3x_1)\,x_2$${}+(x_1y_2-y_1x_2)\,x_3$ multiplies out to six products that cancel in pairs, and the second coordinate cancels in the same way. Dividing by $\Delta$ writes the origin as a weighted average of the corners, with weights that add up to $1$:

$$O=\lambda_A\,A+\lambda_B\,B+\lambda_C\,C,$$

$$\lambda_A=\frac{s_2}{\Delta},\quad\lambda_B=\frac{s_3}{\Delta},\quad\lambda_C=\frac{s_1}{\Delta}.$$

These are the barycentric coordinates of the origin. A point is strictly inside a triangle exactly when all of them are positive; on a side one of them is $0$, and outside at least one is negative. ^[4] Think of masses $\lambda_A$, $\lambda_B$, $\lambda_C$ at the corners, balanced at the origin. For $T_1$ the weights are $\tfrac49$, $\tfrac29$ and $\tfrac39$, and $\tfrac49(-1,-1)+\tfrac29(2,-1)$${}+\tfrac39(0,2)=(0,0)$. For $T_2$ they are $2$, $-\tfrac12$ and $-\tfrac12$: only negative masses move the balance point outside. Since $\lambda_A=s_2/\Delta$ is positive exactly when the origin and $A$ lie on the same side of $BC$, this is the test of Section 4 once more.

6. The two triangles of the statement

For $A=(-340,495)$, $B=(-153,-910)$ and $C=(835,-947)$,

$$\begin{aligned}A\times B&=(-340)(-910)-495\cdot(-153)\\&=309400+75735=385135,\end{aligned}$$

and in the same way $B\times C=144891+759850=904741$ and $C\times A=413325-321980=91345$. All three are positive, so the origin is inside, as the statement says. Their sum $\Delta=1381221$ gives the weights $\lambda_A\approx0.655$, $\lambda_B\approx0.066$ and $\lambda_C\approx0.279$. For $X=(-175,41)$, $Y=(-421,-714)$ and $Z=(574,-645)$ the numbers are $X\times Y=124950+17261=142211$, $Y\times Z=271545+409836=681381$ and $Z\times X=23534-112875=-89341$. The signs are mixed, so the origin is outside. The weight of $Y$ is $-89341/734251\approx-0.122$, so the origin lies beyond the side $ZX$, on the far side from $Y$.

7. Points on the boundary

A zero among $s_1$, $s_2$, $s_3$ puts the origin on the line through a side. The corners $(-1,0)$, $(1,0)$, $(0,1)$ give $0$, $1$, $1$ and the weights $\tfrac12$, $\tfrac12$, $0$: the origin is the midpoint of a side. The corners $(0,0)$, $(1,0)$, $(0,1)$ give $0$, $1$, $0$: the origin is a corner. Three points on a line through the origin, such as $(-1,-1)$, $(1,1)$, $(2,2)$, give $0$, $0$, $0$ and $\Delta=0$: no triangle at all. The interior excludes all these cases, hence the strict inequalities. The weaker rule "no two of the numbers have opposite signs", used by the Python and Java versions, accepts all three, and indeed every triple on a line through the origin, such as $(1,1)$, $(2,2)$, $(3,3)$, where the origin is not even between the points; for a genuine triangle it asks whether the origin is inside or on the boundary. On small grids this matters: of the $2148$ genuine triangles with corner coordinates from $-2$ to $2$, each counted once whatever the order of its corners, the origin is inside $360$ and on the boundary of $656$, so the weaker rule reports $1016$. In the file no $s_i$ is zero, so the two rules give the same count there.

8. Exact whole numbers

The coordinates are whole numbers of size at most $1000$, so every product in a cross product is at most $10^6$ in size and every $s_i$ at most $2\cdot10^6$; the largest $|s_i|$ in the file is $1735129$. This is far below the 32-bit limit $2^{31}-1$, so any integer type of at least 32 bits computes them exactly, and so does floating-point arithmetic, even in single precision, which has $24$ binary digits and stores every whole number below $2^{24}\approx1.7\cdot10^7$ exactly. So the sign test never rounds, which matters, because some triangles come very close to the origin. In the $132$nd triangle of the file, with corners $(-688,-826)$, $(-352,-75)$ and $(371,79)$, the side from the second corner to the third gives $s_2=-27808+27825=17$, while $s_1=-239152$ and $s_3=-252094$. The signs are mixed, so the origin is outside, but only by a hair: by Section 2, twice the area of the triangle formed by the origin and that side is $17$, and the side has length $\sqrt{723^2+154^2}\approx739.2$, so the height of that triangle, the distance of the side from the origin, is $17/739.2\approx0.023$. The cross products decide this with certainty, while the angle sum of Section 9 misses a full turn by only $0.000249$ radians.

9. Three other tests

Areas. The triangles $OAB$, $OBC$ and $OCA$, with areas $|s_1|/2$, $|s_2|/2$ and $|s_3|/2$, fill the triangle exactly when the origin is inside or on the boundary, and stick out otherwise: for $T_1$, $1.5+2+1=4.5$ is its area, while for $T_2$, $1+4+1=6$ is three times its area $2$. In whole numbers the test reads $|s_1|+|s_2|+|s_3|=|\Delta|$, which holds exactly when no two of the numbers have opposite signs, since only opposite signs cancel in the sum $\Delta$: the weaker rule again, which needs a check against zeros, and with floating-point areas a tolerance too.
Angles. Standing at the origin, we measure the angles between the directions of $A$ and $B$, of $B$ and $C$ and of $C$ and $A$, each between $0^\circ$ and $180^\circ$. Inside, and also on a side but not at a corner, where a direction would be undefined, they add up to a full turn: for $ABC$, $135.97^\circ$, $50.95^\circ$ and $173.08^\circ$ give $360^\circ$. Outside, the largest equals the sum of the other two, so the total is smaller: for $XYZ$, $72.66^\circ$, $72.19^\circ$ and $144.85^\circ$ give only $289.70^\circ$. Counted with signs instead, anticlockwise positive, the three turns make one full turn inside, anticlockwise or clockwise as the corners are listed, and cancel outside; for $XYZ$ the last turn is $-144.85^\circ$. The number of full turns is the winding number. ^[5] Both versions need inverse trigonometric functions, and the plain sum also a delicate tolerance: for the $132$nd triangle it falls short of $360^\circ$ by only $0.000249$ radians, so a tolerance of $10^{-3}$ would wrongly count it and the $890$th triangle. The signed sum there is $0$, far from a full turn.
Crossings. A ray from the origin along the positive $x$-axis crosses the boundary once if the origin is inside, and an even number of times otherwise. The same parity rule, odd inside and even outside, holds for every simple polygon, one whose sides meet only where neighbouring sides share a corner, and every point off its boundary. A corner exactly on the ray needs a rule of its own; the usual one treats it as lying slightly above the ray. ^[5] No corner of the file lies on the positive $x$-axis; the only corner on an axis, $(-988,0)$ of the $431$st triangle, would lie on a ray pointing left.

10. One triangle in four

Let us change one corner of $T_1$ at a time into its opposite through the origin. The numbers of $T_1$ are $3$, $4$, $2$. Replacing $C$ by $-C=(0,-2)$ gives $3$, $-4$, $-2$; replacing $B$ by $-B=(-2,1)$ gives $-3$, $-4$, $2$; replacing $A$ by $-A=(1,1)$ gives $-3$, $4$, $-2$. Replacing all three corners turns a whole triangle half a turn about the origin and keeps its numbers, because each $s_i$ contains two corners and changes sign twice. So of the eight triangles with corners $\pm A$, $\pm B$, $\pm C$, the four above and their half-turn images, only $T_1$ and its image $(1,1)$, $(-2,1)$, $(0,-2)$ contain the origin.

The same holds for any three points with nonzero cross products. Replacing $A$ by $-A$ flips the signs of $s_1$ and $s_3$, which contain $A$; replacing $B$ flips $s_1$ and $s_2$, and replacing $C$ flips $s_2$ and $s_3$. These are different pairs, so the triangle and its three one-corner changes have four different sign patterns, which their half-turn images repeat. As every change flips two signs, the sign of $s_1s_2s_3$ never changes: if it is positive, the patterns are $(+,+,+)$, $(+,-,-)$, $(-,+,-)$ and $(-,-,+)$; if it is negative, they are $(-,-,-)$, $(-,+,+)$, $(+,-,+)$ and $(+,+,-)$. Only one of them has three equal signs, so exactly two of the eight triangles contain the origin. If the corners are chosen independently from a distribution that is symmetric about the origin and gives a zero cross product with probability $0$, such as the uniform distribution on a square centred there, the eight triangles are equally likely, and the probability is exactly $\tfrac14$. This is the planar case of Wendel's theorem. Take $N\ge n$ random points in $n$ dimensions, chosen independently from distributions symmetric about the origin, such that with probability $1$ no $n$ of them lie in one hyperplane through the origin: in the plane no two lie on one line through the origin, which is the zero cross product excluded above, and in space no three lie in one plane through the origin. Then the origin lies outside their convex hull, the smallest convex region containing them, with probability ^[6]

$$p=2^{-N+1}\sum_{k=0}^{n-1}\binom{N-1}{k},$$

where $\binom{N-1}{k}$ counts the ways to choose $k$ of $N-1$ things, so that $\binom20=1$ and $\binom21=2$. For $n=2$ and $N=3$

$$p=\frac14\Bigl(\binom20+\binom21\Bigr)=\frac34.$$

On the $25$ grid points with coordinates from $-2$ to $2$, $8640$ of the $15625$ ordered triples have three nonzero cross products, and exactly $2160$ of these, a quarter, contain the origin. Of a million random triangles with corners uniform in a square centred at the origin, a fraction $0.2492$ contained the origin.

11. Beyond triangles

To test a point $P$ instead of the origin, subtract $P$ from every corner first. The proof of Section 4 works for every convex polygon: a point is strictly inside exactly when the cross products of all consecutive corners, taken relative to the point, have one sign. Without convexity this fails: the C-shaped polygon with the corners $(-2,-2)$, $(2,-2)$, $(2,-1)$, $(1,-1)$, $(1,1)$, $(2,1)$, $(2,2)$, $(-2,2)$ contains the origin, yet its cross products are $8,2,-1,2,-1,2,8,8$; there one counts crossings or the winding number. ^[5] In space, Wendel's theorem with $n=3$ and $N=4$ gives $p=\tfrac78$, so a tetrahedron with such random corners contains the origin with probability $\tfrac18$; a simulation of $400000$ tetrahedra with corners uniform in a cube centred at the origin gave $0.1247$.

How the Code Works

The C++ program ^[7] starts in main with the default Options: the file 0102_triangles.txt in the folder resources/documents, relative to the working directory, and the checkpoint switched on. parse_arguments accepts --skip-checkpoints and --file= followed by a path, which parse_string_after_prefix reads; any other argument, or an empty path, gives exit code $1$. run_checkpoints passes the two triangles of the statement to solve_from_text and requires the count $1$, since only $ABC$ contains the origin; otherwise the exit code is $2$. solve reads the whole file into one string for solve_from_text, which skips empty lines and lets parse_csv_i64 split each line at the commas and convert the pieces with std::stoll into the 64-bit type i64. A missing file, or a line without exactly six numbers, ends the program with exit code $3$. contains_origin uses cross, the formula of Section 2, to compute c1, c2, c3, that is $s_1$, $s_2$, $s_3$, and returns true exactly when all three are positive or all three negative, the strict test of Section 4; the number of such triangles is printed.

The Python version looks for the same relative path one level above the folder of the script, whatever the working directory, reads all lines with readlines and converts every field with int. Unlike the other two versions it neither skips blank lines nor checks the number of fields, so a blank line, or a line with five or seven numbers, would stop it with an error; every line of the file holds six numbers. Its inner function contains_origin computes the same c1, c2, c3 and returns not (has_neg and has_pos), the weaker rule of Section 7. The values d1, which is $\Delta$ in the shoelace form, and d2 and the helper sign are never used. Python integers have unlimited precision. ^[8] The Java version reads the file relative to the working directory with Files.readAllLines, skips lines with fewer than six fields and ignores any fields after the sixth, parses the coordinates as int and casts them to long before multiplying, then applies the weaker rule with the flags neg and pos. With 64 bits the cross product is exact for any int coordinates, since its size never exceeds $2^{63}-2^{31}$. ^[8] Only the C++ version runs a checkpoint and uses the strict test; on this file all three give the same count, by Section 7, but Python and Java would also count a triangle with the origin on its boundary, and any three points on a line through the origin.

Complexity and Verification

The test itself costs six multiplications, three subtractions and at most six comparisons per triangle (the Python version also evaluates its unused d1, four more multiplications and five additions or subtractions), so the time grows in proportion to the number of triangles, and reading the text is the largest part of the work. The test needs a fixed amount of memory, but all three programs hold the whole input at once, so their memory grows in proportion to the size of the file: the C++ program keeps its text, about $26$ thousand characters, and Python and Java the list of its lines. In tests on a laptop, the C++ program took about $3$ milliseconds, the Python program about $16$ and the Java program about $50$, most of it for starting the program and reading the file.

The C++ checkpoint checks that exactly one of the two triangles of the statement is counted; it cannot tell which, but Section 6 and the independent checks below show that it is $ABC$. All three programs print the same count, and small test files confirm the differences between them described above. Independent checks, not part of the published solutions: on all $1000$ triangles of the file the sign test agrees with exact barycentric weights, with the comparison with the opposite corners of Section 4, with the area test, with an exact crossing count, with the floating-point angle sum at tolerance $10^{-9}$ and with the signed sum of the turns, for all six orders of the corners. The file has no zero cross product, no repeated corner and no three corners on one line, and it begins with the two triangles of the statement. On the grids with coordinates from $-R$ to $R$ for $R=1,2,3$, we checked all $134003$ ordered triples of points, repeated points included: the strict test agrees on every one with an exact classification by barycentric weights, in which the triples with $\Delta=0$ have no interior, and on each grid exactly a quarter of the triples with three nonzero cross products contain the origin.

Footnotes and References

The references below supply the background facts used above. The side test, the identity $\Delta=s_1+s_2+s_3$, the weights of the origin, the treatment of the boundary and the one-quarter law are derived explicitly in this article.

Project Euler 102 — Triangle Containment. The official statement: three distinct points with −1000 ≤ x, y ≤ 1000 form a triangle; ABC contains the origin and XYZ does not; triangles.txt holds one thousand "random" triangles, the first two being these, and the task is to count those whose interior contains the origin.
Wikipedia — Determinant. For a 2 × 2 matrix, |ad − bc| is the area of the parallelogram spanned by the columns, so the determinant is a signed area: positive when the first column turns anticlockwise to the second, negative for a clockwise turn, and zero when the vectors are aligned.
Wikipedia — Shoelace formula. Its triangle form adds the oriented areas of the triangles formed by a fixed point and two consecutive vertices, each half a 2 × 2 determinant; the result is positive for vertices listed anticlockwise and negative for clockwise ones.
Wikipedia — Barycentric coordinate system. Normalised barycentric coordinates add up to 1 and are ratios of signed areas; all of them are positive exactly when the point is strictly inside the triangle, one is zero on an edge, and at least one is negative outside.
Wikipedia — Point in polygon. For a simple polygon, a ray from an inside point crosses the boundary an odd number of times and a ray from an outside point an even number, where a vertex on the ray counts as lying slightly above it. The angles subtended by the edges add up to a multiple of 2π, namely 2π times the winding number; summing them directly needs costly inverse trigonometric functions, which tracking the quadrants or counting signed crossings avoids. In floating-point arithmetic, rounding errors can misclassify points very close to the boundary.
Wikipedia — Wendel's theorem. N random points on a sphere in n dimensions lie on one half of it, that is, the origin is not in their convex hull, with probability 2^(−N+1) times the sum of C(N − 1, k) for k = 0, …, n − 1. The page states this for any distribution symmetric around the origin; its source, J. G. Wendel, Math. Scand. 11 (1962), 109–111, proves it for random vectors whose joint distribution does not change when any of them is reflected through the origin and of which, with probability 1, every n are linearly independent.
C++ — Euler102.cpp. The linked immutable C++ revision contains cross, contains_origin, the two options and the checkpoint. It is the implementation record for this article.
Java Language Specification — Types, Values, and Variables. int and long are 32-bit and 64-bit two's-complement integers, integer operators do not indicate overflow, and an operation with a long operand uses 64-bit precision. Python — numeric types: integers have unlimited precision.

Problem 102 source code

C++

#include <cstdint>
#include <fstream>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    std::string file = "resources/documents/0102_triangles.txt";
    bool run_checkpoints = true;
};

struct Point {
    i64 x = 0;
    i64 y = 0;
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--file=", options.file)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return true;
}

i64 cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

bool contains_origin(const Point& a, const Point& b, const Point& c) {
    const i64 c1 = cross(a, b);
    const i64 c2 = cross(b, c);
    const i64 c3 = cross(c, a);

    const bool all_positive = (c1 > 0 && c2 > 0 && c3 > 0);
    const bool all_negative = (c1 < 0 && c2 < 0 && c3 < 0);
    return all_positive || all_negative;
}

std::vector<i64> parse_csv_i64(const std::string& line) {
    std::vector<i64> values;
    std::istringstream input(line);
    std::string token;
    while (std::getline(input, token, ',')) {
        values.push_back(std::stoll(token));
    }
    return values;
}

int solve_from_text(const std::string& text) {
    std::istringstream input(text);
    std::string line;
    int count = 0;

    while (std::getline(input, line)) {
        if (line.empty()) {
            continue;
        }
        const std::vector<i64> v = parse_csv_i64(line);
        if (v.size() != 6) {
            throw std::runtime_error("Malformed triangle row");
        }

        const Point a{v[0], v[1]};
        const Point b{v[2], v[3]};
        const Point c{v[4], v[5]};
        if (contains_origin(a, b, c)) {
            ++count;
        }
    }

    return count;
}

int solve(const std::string& file_path) {
    std::ifstream input(file_path);
    if (!input) {
        throw std::runtime_error("Could not open triangles file: " + file_path);
    }

    std::ostringstream buffer;
    buffer << input.rdbuf();
    return solve_from_text(buffer.str());
}

bool run_checkpoints() {
    const std::string sample =
        "-340,495,-153,-910,835,-947\n"
        "-175,41,-421,-714,574,-645\n";

    if (solve_from_text(sample) != 1) {
        std::cerr << "Checkpoint failed for statement sample" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.file) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

# Problem 102: Triangle containment
# How many triangles in the file contain the origin?

import os

def solve():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    file_path = os.path.join(script_dir, '..', 'resources', 'documents', '0102_triangles.txt')
    
    def contains_origin(x1, y1, x2, y2, x3, y3):
        # Cross product method
        d1 = x1 * (y2 - y3) - y1 * (x2 - x3) + (x2 * y3 - x3 * y2)
        d2 = 0  # sub-triangles with origin
        # Check using sign of cross products
        def sign(x):
            return (x > 0) - (x < 0)
        def cross(ax, ay, bx, by):
            return ax * by - ay * bx
        
        c1 = cross(x1, y1, x2, y2)
        c2 = cross(x2, y2, x3, y3)
        c3 = cross(x3, y3, x1, y1)
        
        has_neg = (c1 < 0) or (c2 < 0) or (c3 < 0)
        has_pos = (c1 > 0) or (c2 > 0) or (c3 > 0)
        return not (has_neg and has_pos)
    
    with open(file_path) as f:
        lines = f.readlines()
    
    count = 0
    for line in lines:
        coords = list(map(int, line.strip().split(',')))
        if contains_origin(*coords):
            count += 1
    print(count)

solve()

Java

import java.nio.file.*;
import java.util.*;

public class Euler102 {
    public static void main(String[] args) throws Exception {
        List<String> lines = Files.readAllLines(Path.of("resources/documents/0102_triangles.txt"));
        int count = 0;
        for (String line : lines) {
            String[] p = line.trim().split(",");
            if (p.length < 6)
                continue;
            int x1 = Integer.parseInt(p[0]), y1 = Integer.parseInt(p[1]), x2 = Integer.parseInt(p[2]),
                    y2 = Integer.parseInt(p[3]), x3 = Integer.parseInt(p[4]), y3 = Integer.parseInt(p[5]);
            long c1 = (long) x1 * y2 - (long) y1 * x2, c2 = (long) x2 * y3 - (long) y2 * x3,
                    c3 = (long) x3 * y1 - (long) y3 * x1;
            boolean neg = c1 < 0 || c2 < 0 || c3 < 0, pos = c1 > 0 || c2 > 0 || c3 > 0;
            if (!(neg && pos))
                count++;
        }
        System.out.println(count);
    }
}