C: Magic Bullet 担当: 川満.

C: Magic Bullet 担当: 川満

問題概要 3次元空間に𝑁 ≤50 個の球状の障害物が与えられるある座標からある目標の座標に向かって弾を撃つ
3次元空間に𝑁 ≤50 個の球状の障害物が与えられるある座標からある目標の座標に向かって弾を撃つ弾に魔力があれば障害物を貫通できる目標の座標に届かせるために必要な魔力の量は?

解法３次元幾何問題線分と球の交差判定ができればよい解法の例球の中心座標が原点になるように線分を平行移動
線分を通る直線上の点のうち、原点に最も近い点を求める求めた点が線分上にあり、かつ求めた点と原点との距離が球の半径以下かを判定する

直線上の点で原点に最も近い点点sおよび点tを通る直線を考える点sから点tに向かうベクトルを 𝑣 とする
原点から点sに向かうベクトルを 𝑠 とすると、直線上の点pは変数𝑥を用いて、 𝑠 +𝑥 𝑣 となる 𝑣 点t

直線上の点で原点に最も近い点原点と点pの距離の2乗を𝑓(𝑥)とすると、𝑓 𝑥 = 𝑠 +𝑥 𝑣 2 となる

ジャッジ解 63行、1181 bytes

Results FA: 動画勢「まさかの3000AC」 (18:50)
28 ACs, 29 trying teams, 50 submissions

Presentation on theme: "C: Magic Bullet 担当: 川満."— Presentation transcript: