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
Last-modified: 2011-06-24 (金) 18:16:24 (2195d)