Problem 165

Intersections

A segment is uniquely defined by its two endpoints.

By considering two line segments in plane geometry there are three possibilities:

the segments have zero points, one point, or infinitely many points in common.

Moreover when two segments have exactly one point in common it might
be the case that that common point is an endpoint of either one of the
segments or of both. If a common point of two segments is not an
endpoint of either of the segments it is an interior point of both
segments.

We will call a common point T of two segments L_{1} and L_{2} a true intersection point of L_{1} and L_{2} if T is the only common point of L_{1} and L_{2} and T is an interior point of both segments.

Consider the three segments L_{1}, L_{2}, and L_{3}:

L_{1}: (27, 44) to (12, 32)

L_{2}: (46, 53) to (17, 62)

L_{3}: (46, 70) to (22, 40)

It can be verified that line segments L_{2} and L_{3} have a true intersection point. We note that as the one of the end points of L_{3}: (22,40) lies on L_{1} this is not considered to be a true point of intersection. L_{1} and L_{2} have no common point. So among the three line segments, we find one true intersection point.

Now let us do the same for 5000 line segments. To this end, we generate 20000 numbers using the so-called "Blum Blum Shub" pseudo-random number generator.

s_{0} = 290797

s_{n+1} = s_{n}s_{n} (modulo 50515093)

t_{n} = s_{n} (modulo 500)

To create each line segment, we use four consecutive numbers t_{n}. That is, the first line segment is given by:

(t_{1}, t_{2}) to (t_{3}, t_{4})

The first four numbers computed according to the above generator should be: 27, 144, 12 and 232. The first segment would thus be (27,144) to (12,232).

How many distinct true intersection points are found among the 5000 line segments?

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**