> For the complete documentation index, see [llms.txt](https://project-euler-ja.gitbook.io/project-euler-ja/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://project-euler-ja.gitbook.io/project-euler-ja/101-200/161-170/p165.md).

# 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個の線分に対して、相異なる真の交点はいくつあるか？