2015年5月9日土曜日

AOJ 2586 : 流れ星に願いを

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2586
空間上にn個の球がある。
それぞれの球は速度(vx,vy,vz)で移動し1秒でvrだけ半径が減少し、
二つの球が接触もしくは半径<=0になったらその球は消滅する。

それぞれの球が消滅するまでの時間を求めよ。

解法

まず二つの球が接触するかどうかを判定するために球iと球jのt秒後の距離をf(t)とおくと
f(t)は下に凸な関数になっているので三分探索を使って極小値を求める。この極小値が0以下ならば二つの球は接触するので、極小値を与えるtと0との間で二分探索をすれば良い。

こうすれば接触時間と消滅時間がわかるので、それらの時間をソートして最初に起こるイベントから順に処理していけば良い。

・・・よく考えたら接触時間は二次方程式になるので三分探索する必要はなかった。

ソースコード

https://gist.github.com/knewknowl/9913126a26b210230e4d

0 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...