165 : 交点

線分は二つの端点によって一意に決まる。 平面上の2つの線分を考えると以下の3つの可能性がある： 共有点が0個の場合、共有点が1個の場合、無限に多くの共有点を持つ場合。

さらに、2つの線分が共有点を1つのみ持つとき、共有点がどちらかまたは両方の線分の端点である場合がある。もし共有点がどちらの線分の端点でもないなら、その点は両方の線分の内部の点である。 もし、線分 L1 と L2 の共有点 $T$ が $L_1$ と $L_2$ の唯一の共有点であり、両方の線分の内部の点であるとき、$T$ を真の交点と呼ぶことにする。

次の3つの線分 $L_1, L_2, L_3$ を考える。

$L_1$: (27, 44) から (12, 32) $L_2$: (46, 53) から (17, 62) $L_3$: (46, 70) から (22, 40)

$L_2$ と $L_3$ は真の交点を持つことが確かめられる。$L_3$ の1つの端点の(22,40)は $L_1$ 上にあるが、これは真の交点とならないことに注意せよ。$L_1$ と $L_2$ は共有点を持たない。つまり、上の3つの線分では、真の交点は1つとなる。

いま、同じことを5000個の線分に対して行うことにする。そのために、20,000個の数を "Blum Blum Shub" と呼ばれる擬似乱数生成法によって生成する。

$s_0 = 290797$ $s_{n+1} = s_n × s_n \bmod 50515093$ $t_n = s_n \bmod 500$

それぞれの線分を4つの連続する $t_n$ によって決める。つまり、最初の線分は $(t_1, t_2)$ から $(t_3, t_4)$ と与えられる。（訳注：$s_0, t_0$ は使わない。）

最初の4つの数は上の生成法によって 27, 144, 12, 232 となる。最初の線分は (27,144) から (12,232) となる。

上の5000個の線分に対して、相異なる真の交点はいくつあるか？