SRM401 550 : ParticleCollision

年度末までにSRMdiv1 easy medium 100回分やるぞ

記念すべき第一回の med (結構詰まった問題だったり印象に残った問題はメモとして書いてきます。)

早速幾何恐怖症を植え付けられそうになった。

問題概要

• ３次元の座標軸があります。
• 螺旋上の軌跡を描く粒子があります。
  x = cos(t);
  y = sin(t);
  z = t;
  ある時間tでの座標はこのように表される。
• 入力として直線の軌跡を描く粒子が
  単位時間辺りの移動距離(vx,vy,vz)と初期座標の (x0,y0,z0)として与えれます。
• 2つの粒子の軌跡が交差する点がひとつであればその座標を、
  複数あれば(0.0,0.0,0.0)を、一つもなければ空のvectorを返して下さい。
• 軌跡の交差なので、tが-の場合もあることに注意

解法

• 幾何ゲー
• 円と直線の交点を求めるライブラリ使ってとりあいず交点を求める。
• その点での直線移動粒子のZ座標を調べて、螺旋粒子と比較。
• 特殊なケースとしてvxとvyがともに0のときに場合わけを行う。
  vz = 0 のときはその点が螺旋状にあるかを判定
  vz != 0 のときはXY平面のみを見て円上にあるかを判定する

ソースコード

感想

そもそも軌跡の交差ではなく、実際にの衝突判定を行うと誤読していた。

trajectories　という単語があって調べたら軌跡という意味だった。

要注意英単語もメモっとくべきだろこれ

英単語

trajectories: 軌跡