- All Contests
- ProjectEuler+
- Project Euler #165: Intersections

# Project Euler #165: Intersections

# Project Euler #165: Intersections

_{This problem is a programming version of Problem 165 from projecteuler.net}

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 and a true intersection point of and if is the only common point of and and is an interior point of both segments.

Consider the three segments :

It can be verified that line segments and have a true intersection point. We note that as the one of the end points of lies on this is not considered to be a true point of intersection. and have no common point. So among the three line segments, we find one true intersection point.

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

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

The first four numbers computed according to the above generator should be: . The first segment would thus be .

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

**Input Format**

One integer is given on first line representing .

**Constraints**

**Output Format**

Print one integer which is the answer to the problem.

**Sample Input 0**

```
10
```

**Sample Output 0**

```
5
```