Detailed mathematical approach

Problem Summary

Problem 165 asks for the number of distinct true intersection points among 5000 line segments generated by a deterministic pseudo-random process. Each segment is determined by four consecutive values from the sequence, so the geometric input is fixed even though it looks random.

A true intersection means a single point that lies strictly inside both segments. Endpoint touches are excluded, and collinear overlaps are excluded as well. The two real difficulties are deciding that strict condition correctly for every pair of segments and making sure that the same geometric point is not counted twice when different segment pairs meet there.

Mathematical Approach

The solution has four mathematical ingredients: generating the segments, testing whether two segments cross in their interiors, computing the crossing point exactly, and storing those points in a canonical form so duplicates collapse automatically.

The Deterministic Segment Family

The sequence used by the problem is

$s_0=290797,\qquad s_{n+1}=s_n^2 \bmod 50515093,$

and then

$t_n=s_n \bmod 500.$

The \(n\)-th segment is therefore

$L_n=\bigl((t_{4n-3},t_{4n-2}),(t_{4n-1},t_{4n})\bigr),\qquad 1\le n\le 5000.$

All coordinates are integers between 0 and 499, so every segment endpoint lies on the integer lattice inside a \(500\times500\) box. That bounded integer structure is what makes an exact integer-and-rational solution practical.

Strict Interior Intersection via Oriented Area

For three points \(A\), \(B\), \(C\), define the signed area determinant

$\Delta(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$

The sign of \(\Delta(A,B,C)\) tells us on which side of the directed line \(AB\) the point \(C\) lies. For two segments \(AB\) and \(CD\), a proper interior crossing occurs exactly when \(C\) and \(D\) lie on opposite sides of line \(AB\), and simultaneously \(A\) and \(B\) lie on opposite sides of line \(CD\). In formulas,

$\operatorname{sgn}(\Delta(A,B,C))\operatorname{sgn}(\Delta(A,B,D)) \lt 0,$

$\operatorname{sgn}(\Delta(C,D,A))\operatorname{sgn}(\Delta(C,D,B)) \lt 0.$

The strict inequality is the key detail. If one determinant is zero, then one endpoint lies on the other supporting line, which means an endpoint touch or a collinear case rather than a true interior intersection. So the test used by the implementations rejects all non-strict cases automatically.

The Equivalent Parameter Form

The same condition can be written parametrically. Write

$P(t)=A+t(B-A),\qquad Q(u)=C+u(D-C).$

If the two supporting lines are not parallel, there is a unique solution of

$A+t(B-A)=C+u(D-C).$

With \(r=B-A\) and \(s=D-C\), the denominator is the 2D determinant

$\operatorname{den}=r\times s,$

and the numerators are

$t_{\text{num}}=(C-A)\times s,\qquad u_{\text{num}}=(C-A)\times r.$

Then the crossing point lies strictly inside both segments exactly when

$0 \lt \frac{t_{\text{num}}}{\operatorname{den}} \lt 1,\qquad 0 \lt \frac{u_{\text{num}}}{\operatorname{den}} \lt 1,$

after interpreting the inequalities with the sign of \(\operatorname{den}\). One implementation uses this form directly, while the others use the orientation-sign version above. They are the same determinant test written in two different languages of geometry.

Exact Coordinates of the Intersection Point

Once two segments are known to intersect properly, the intersection point must be stored exactly. Floating-point coordinates would be risky here because two algebraically identical points can arrive through different segment pairs and round slightly differently.

For the line through \(A=(x_1,y_1)\) and \(B=(x_2,y_2)\), write

$a_1=y_2-y_1,\qquad b_1=x_1-x_2,\qquad c_1=a_1x_1+b_1y_1,$

and similarly for the line through \(C=(x_3,y_3)\) and \(D=(x_4,y_4)\):

$a_2=y_4-y_3,\qquad b_2=x_3-x_4,\qquad c_2=a_2x_3+b_2y_3.$

Then Cramer's rule gives

$\operatorname{den}=a_1b_2-a_2b_1,$

$x=\frac{c_1b_2-c_2b_1}{\operatorname{den}},\qquad y=\frac{a_1c_2-a_2c_1}{\operatorname{den}}.$

The denominator is normalized to be positive, and then the \(x\)-coordinate and \(y\)-coordinate are each reduced by their own greatest common divisor. The canonical representation is therefore the quadruple

$\left(\frac{x_{\text{num}}}{x_{\text{den}}},\frac{y_{\text{num}}}{y_{\text{den}}}\right),$

stored as four integers \((x_{\text{num}},x_{\text{den}},y_{\text{num}},y_{\text{den}})\). Because the fractions are reduced and denominators are made positive, equal geometric points receive exactly the same key.

Worked Example from the Stated Sample

The sample segments

$((46,53),(17,62))\quad\text{and}\quad((46,70),(22,40))$

produce the unique true intersection among the three sample segments checked by the implementation.

For these two segments,

$r=(-29,9),\qquad s=(-24,-30),\qquad \operatorname{den}=r\times s=1086.$

Also \(C-A=(0,17)\), so

$t_{\text{num}}=(C-A)\times s=408,\qquad u_{\text{num}}=(C-A)\times r=493.$

Since

$0 \lt 408 \lt 1086,\qquad 0 \lt 493 \lt 1086,$

the intersection is strictly interior to both segments. Using \(A+t(B-A)\) with \(t=408/1086=68/181\), we get

$x=46-\frac{29\cdot68}{181}=\frac{6354}{181},\qquad y=53+\frac{9\cdot68}{181}=\frac{10205}{181}.$

That exact rational point is what gets inserted into the set. Any later segment pair producing the same point would reduce to the same canonical quadruple and would therefore not be counted twice.

Why a Set of Rational Points Solves the Counting Problem

The problem does not ask for the number of intersecting segment pairs. It asks for the number of distinct true intersection points. Several different pairs can meet at the same point, so after a pair passes the strict crossing test, the correct mathematical object to store is the point itself, not the pair. The implementations therefore turn every valid crossing into one exact rational point and let the set structure remove duplicates.

How the Code Works

Generate the 5000 Segments

The C++, Python, and Java implementations begin by generating the deterministic sequence, reducing each term modulo 500, and grouping every four values into one segment. This reproduces the problem input exactly and avoids any dependence on floating-point randomness or external data.

Scan Every Pair and Apply the Strict Crossing Test

The main loop examines all \(\binom{5000}{2}\) unordered pairs of segments. The C++ and Python implementations evaluate the four oriented-area determinants and require opposite signs on both sides. The Java implementation computes the same geometry through the denominator and the two segment parameters, then checks that both parameters lie strictly between 0 and 1. Although the formulas look different, both approaches reject parallel pairs, endpoint touches, and overlaps for the same mathematical reason.

Compute an Exact Key for Each Valid Intersection

Whenever a pair truly intersects, the implementation computes the point with integer arithmetic and reduces the resulting rational coordinates. The C++ and Python implementations store the reduced quadruple directly in an ordered set. The Java implementation reduces the same rational data and compresses it into a hashable key for a hash set. In all three cases, the canonicalized rational representation is the mechanism that turns repeated geometric points into one stored object.

Complexity Analysis

With \(N=5000\) segments, the algorithm checks

$\binom{5000}{2}=12{,}497{,}500$

segment pairs, so the running time is \(O(N^2)\). Each pair requires only constant-time integer arithmetic, plus a few \(\gcd\) reductions when an actual intersection is found.

Memory usage is \(O(N+K)\), where \(N\) accounts for the stored segments and \(K\) is the number of distinct true intersection points that survive de-duplication. For this problem size, the quadratic scan is entirely feasible, and the exact-rational storage keeps the count mathematically correct.

Footnotes and References

1. Project Euler Problem 165: https://projecteuler.net/problem=165
2. Line segment intersection by orientation tests: cp-algorithms - Check if two segments intersect
3. Line-line intersection formulas: Wikipedia - Line-line intersection
4. Cross product and determinants in planar geometry: Wikipedia - Cross product
5. Greatest common divisor: Wikipedia - Greatest common divisor
6. Blum Blum Shub background for the generator family: Wikipedia - Blum Blum Shub