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