*[[Problem 165:http://projecteuler.net/index.php?section=problems&id=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個の線分に対して、いくつの相異なった真の交点が存在するか?


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS