*[[Problem 165:http://projecteuler.net/problem=165]] 「交点」 [#c3b60de7]
線分は二つの端点によって一意に決まる. ~
平面上の2つの線分を考えると以下の3つの可能性がある, ~
共有点が0個のケース, 共有点が1個のケース, 無限に多くの共有点を持つケース.
さらに, 2つの線分が共有点を1つのみ持つとき, 共有点がどちらかまたは両方の線分の端点である場合がある. もし共有点がどちらの線分の端点でもないなら, その点は両方の線分の内部の点である. ~
もし, 線分 &tex{L_{1}}; と &tex{L_{2}}; の共有点Tが &tex{L_{1}}; と &tex{L_{2}}; の唯一の共有点であり, 両方の線分の内部の点であるとき, Tを真の交点と呼ぶことにする.
3つの線分 &tex{L_{1}, L_{2}, L_{3}}; を考える.
&tex{L_{1}};: (27, 44) から (12, 32)~
&tex{L_{2}};: (46, 53) から (17, 62)~
&tex{L_{3}};: (46, 70) から (22, 40)~
&tex{L_{2}}; と &tex{L_{3}}; は真の交点を持つことが確かめられる. &tex{L_{3}}; の1つの端点の(22,40)は &tex{L_{1}}; 上にあるが, これは真の交点とならないことに注意. &tex{L_{1}}; と &tex{L_{2}}; は共有点を持たない. つまり上の, 3つの線分では, 真の交点は1つとなる.
いま, 同じことを5000個の線分に対して行うことにする. そのために, 20000個の数を"Blum Blum Shub"と呼ばれる擬似乱数生成法によって生成する.
&tex{s_{0} = 290797};
&tex{s_{n+1} = s_{n}×s_{n} (modulo 50515093)};
&tex{t_{n} = s_{n} (modulo 500)};
それぞれの線分を4つの連続する &tex{t_{n}}; によって決める. つまり, 最初の線分は,
&tex{(t_{1}, t_{2})}; から &tex{(t_{3}, t_{4})}; と与えられる.
最初の4つの数は上の生成法によって, 27, 144, 12, 232 となる. 最初の線分は, (27,144) から (12,232) となる.
上の5000個の線分に対して, いくつの相異なった真の交点が存在するか?
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
