Problem 165 の編集

*[[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個の線分に対して, いくつの相異なった真の交点が存在するか?

タイムスタンプを変更しない