« ぐあー、ぶちまけてぇ | Main | プログラマーになりたい人向きの頭の柔軟体操 (解答編) »

June 09, 2006

プログラマーになりたい人向きの頭の柔軟体操

存在を知って以来、もうすっかりファンになってしまった、中島聡さんの「Life is Beautiful」、「ミネラルウォーターの謎、謎解き編」より。

【問題】ある直線上に線分AとBがあります。線分Aの両端の座標はそれぞれA0とA1(ただしA0<A1)、線分Bの端の座標はそれぞれB0とB1 (ただしB0<B1)とします。そのとき、線分Aと線分Bが一部でも重なる(一点だけで接している場合も重なっているとみなす)ための条件を出来るだけ簡単な式で書いてください。式は純粋な数式でも良いし、プログラム言語の一つを使ってもOK。
私はすでにプログラマなので、すいすいと解けました。


...ということにしておいてください(苦笑)。ちらっと「まずい方向」に考えかけてしまいました。すぐにひらめいたけど。

以下、私なりの解答。もちろんこれが「唯一の解」ではない。

--

向こうのコメントにも書いてしまったけれど、基本的な考え方は
「両端の座標をたすきがけにペアにして、位置関係を見る」

「ベクトル(B1→A0)、(B0→A1)の向きが一致しているかどうかを見る」。一致していれば「重なってない」。
(A0→B1)、(A1→B0)と逆に書いてもOK。私は気分的に(B→A)のほうがしっくりくる。
点が重なっているときは、ゼロベクトルになるので、向きは「ない」...よね ? (違ったかな)

具体的に式にすると、(B1-A0)と(B0-A1)の符号が合っているかどうか。合っていれば「重なっていない」。
どちらか一方でも0なら重なっている。

ここで、「2つの値の符号が同じかどうか」は複数回比較(0も考慮するとちょっと多い ?)してもいいけど、その値同士を掛け合わせた値の正負を見れば、比較は1回で済む。
(比較演算のコストが高かった頃のアセンブラプログラミングの癖 ^^;)

よって、

if (B1-A0)*(B0-A1) > 0 then 重なっていない
else 重なっている

が簡潔でいいのではないかと。

|

« ぐあー、ぶちまけてぇ | Main | プログラマーになりたい人向きの頭の柔軟体操 (解答編) »

Comments

Post a comment



(Not displayed with comment.)


Comments are moderated, and will not appear on this weblog until the author has approved them.



TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/6718/10450495

Listed below are links to weblogs that reference プログラマーになりたい人向きの頭の柔軟体操:

« ぐあー、ぶちまけてぇ | Main | プログラマーになりたい人向きの頭の柔軟体操 (解答編) »