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

Consider the three segments L₁, L₂, and L₃:

L₁: (27, 44) to (12, 32)
L₂: (46, 53) to (17, 62)
L₃: (46, 70) to (22, 40)

It can be verified that line segments L₂ and L₃ have a true intersection point. We note that as the one of the end points of L₃: (22,40) lies on L₁ this is not considered to be a true point of intersection. L₁ and L₂ 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₀ = 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₁, t₂) to (t₃, t₄)

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?

交点

一条线段由其两个端点唯一决定。考虑平面几何中的两条线段，一共有如下三种可能性：
两条线段没有、有一个或者有无数个交点。

进一步地，当两条线段恰好有一个交点时，可能这个交点是其中一条或两条的端点。如果这个交点不是任一条线段的端点，那它一定是这两条线段的内点。
当两条线段L₁和L₂的交点T是这两条线段唯一的交点且是这两条线段的内点时，我们称T为这两条线段的真交点。

考虑以下三条线段L₁，L₂和L₃：

L₁: (27, 44) to (12, 32)
L₂: (46, 53) to (17, 62)
L₃: (46, 70) to (22, 40)

可以验证，线段L₂和L₃有一个真交点。注意到L₃的一个端点(22,40)恰好在L₁上，因此这不是一个真交点。L₁和L₂则没有交点。因此在这三条线段中，一共有一个真交点。

现在我们来对5000条线段求真交点数。首先，我们用“布鲁姆-布鲁姆-舒布”伪随机数生成算法生成20000个数。

s₀ = 290797
s_n+1 = s_n×s_n (modulo 50515093)
t_n = s_n (modulo 500)

为了生成每一条线段，我们使用t_n的连续四项，也就是说，第一条线段是：

(t₁, t₂)至(t₃, t₄)

由上述算法生成的前四个数是：27，144，12和232，因此第一条线段是(27,144)至(12,232)。

在这5000条线段中，有多少个真交点？