Problem 165

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

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

3つの線分 L1, L2, L3 を考える。

L1: (27, 44) から (12, 32)
L2: (46, 53) から (17, 62)
L3: (46, 70) から (22, 40)

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

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

s0 = 290797

sn+1 = sn×sn (modulo 50515093)

tn = sn (modulo 500)

それぞれの線分を4つの連続する tn によって決める。つまり、最初の線分は、

(t1, t2) から (t3, t4) と与えられる。

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

上の5000個の線分に対して、いくつの相異なった真の交点が存在するか?


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