CGL_2_D: Distance
線分と線分の間の距離を求める問題
こんな図が出ている
射影が使えそうな図ではあるけれども
射影が線分の上に落ちなかったら?
射影が線分上にあるっていう条件が不要なのなら
線分じゃなくて直線って書くはずだし・・・
って直線だったら交わっちゃうか
っていうか線分だって交わるときあるね?
そういうときは距離は0ってことでいいのかな?
そもそも線分の間の距離って何だろう
線分上の点どうしの距離の中でいちばん小さいもの、でいいよな
だとすれば交われば0
あとこういう場合も考えられる
このときは近い方の端点間の距離
場合分けがいりそうだ
少なくとも交わる場合は別で考える必要がありそう
交わらない場合は、4つの端点から相手の線分に射影を落として、
線分上に落ちたもののうち最短のものを取る
どれも相手の線分上に落ちなければ、端点間の距離のうち最短のもの
そんな感じかな
もっときめ細かに場合分けすれば「のうち最短のもの」ってしなくても
よくなるかもしれないけどまずはこれくらいでいいんじゃないか
TLE出てから考えよう
ってところで具体的な計算に入る(のは明日にしよう
ヒントには内積と外積を使うっぽく書いてあるので
使いどころを考えながらやろう
内積は射影でも使ったし、角度(cosθ)を出すのによく使った
外積は何に使えばいいんだろう
平行四辺形の面積になるって言ってるけど、直接使う雰囲気ではない
sinθを求めたくなることはあるかな
わからん
計算はやればできそうな気はするけどすぐできる感じでもない
思考★なんだけどなあ
もっと簡単にできないかなあ