Document

Save the Energy
問題作成:泉
解答作成:荒木、村主
英訳:泉
解説:荒木
問題の説明
• 三次元空間に直線が何本
かある。
• 直線上はエネルギー0で動
ける。
• 直線間を動くためには、移
動距離分だけエネルギー
が必要。
• startからgoalまで移動する
のに必要なエネルギーの
最小値を求める。
– startとgoalは必ず直線上に
ある。
z
start
y
goal
0
x
解法
• 各直線間の最短距離を求めて、それを枝の
長さとする無向グラフ(今回は完全グラフ)を
作り、ダイクストラのアルゴリズムで求める。
– 今回は完全グラフなので
– (疎なグラフの場合は
)
• E…枝の数、V…点の数
• 問題なのは、各直線間の最短距離の求め方。
直線間の最短距離の求め方①
• ベクトルを使って求める方
法。
http://oshiete1.goo.ne.jp/k
otaeru.php3?q=77895 よ
り。
• ～^は単位ベクトル
• ～_はベクトル
• Aaは直線Aとxy平面との交
点
• Bbは直線Bとxy平面との交
点
B
z
A
b^
a^
y
Bb
Aa
0
求める距離dと
それに平行な単
位ベクトルn^
c_
α
β
x
• n^⊥a^,n^⊥b^
• n^=a^×b^/|a^×b^|
(×は外積)
• αa^+dn^=c_+βy^
• よってαa^n^+dn^n^
=c_n^+βb^n^
• ∴d=c_n^
B
z
A
b^
a^
y
Bb
Aa
0
求める距離dと
それに平行な単
位ベクトルn^
c_
α
β
x
• ただし、AとBが平行の
時はn^を
a^×b^/|a^×b^|として
求めることができない。
• そのような場合は、A上
の一点とBとの距離とし
て求める。平行なので、
A上の一点はどこでも
良い。
p
A
x_
d
B
q
y^
適当な二点p,qについて、
上図のようにベクトルx_と
単位ベクトルy^をとると、
平行四辺形の面積
=垂線の長さd
=|x_×y^|
直線間の最短距離の求め方②
• 微分を使う方法
• (x1,y1,z1)+t(dx,dy,dz)と
(x2,y2,z2)との距離を求
める
• その距離をtについて微
分し、それが0となるtを
求める。
B
z
(x3,y3,z3)
A
(x1,y1,z1)
(ex,ey,ez)
(dx,dy,dz)
y
(x2,y2,z2)
0
x
• (x2,y2,z2)=
(x3,y3,z3)+s(ex,ey,ez)
を先ほど求めた距離の
式(tは微分=0のものを代
入)に代入し、sについて
微分し、それが0となるs
を求める。
• 求めたsから距離を求め
る。
B
z
(x3,y3,z3)
A
(x1,y1,z1)
(ex,ey,ez)
(dx,dy,dz)
y
(x2,y2,z2)
0
• 微分を使う方法でも、平行の場合は点と直線
との距離で求めないといけない(∵二回目の微
分が0となるsが無数にあるから)。
• 式が非常に複雑になるので、ベクトルを使う
方がよいと思われる。
結果
• Submit:7
• Accept:4(first accept 64min)
• ちなみに僕の予想はAccept:3でした。
余談
• コンテスト開始直前に、ジャッジプログラムの
一つが-O2オプションをつけるとおかしくなる
ことが判明し、ゴタゴタしました。すいません。

Download Report