I always have WA.

The idea is simple: get derivative from distance.
assume a1=x[i]-x[j],a2=y[i]-y[j],a3=z[i]-z[j], b1 = vx[i]-vx[j],b2 = vy[i]-vy[j],b3 = vz[i]-vz[j].

Then we should solve quadric equation ax^2+bx+c to find time, where a=a = (b1*b1+b2*b2+b3*b3), b = 2*(a1*b1+a2*b2+a3*b3), c = (a1*a1+a2*a2+a3*a3)-d;

where i'm wrong?

Edited by author 02.03.2008 22:32

it's right
if d = d * d
check negative roots
be careful with float point

try this random test

4 15.0
15.0 1.4 -3.0 3.0 54.0 130.0
65.0 23.0 4.0 5.0 3.0 34.4
23.0 57.0 5.0 8.0 4.0 31.4
7.0 34.0 7.0 123.0 76.0 54.4


ALARM!
0.124 3 4


Edited by author 03.03.2008 04:35

Edited by author 03.03.2008 04:36

Please give me tests when the roots are negative!!

it's not hard

2 0.1
0 1 0 1 1 0
0 0 0 1 -1 0

OK

roots -0.45 and -0.55

one more test(with positive roots)

2 0.1
-10000 -10000 0  0.1  0.1 0
-10000 10000  0 0.1 0 0

ALARM!
199999.000 1 2

Edited by author 03.03.2008 23:43

Edited by author 03.03.2008 23:43

Why we should check negative roots if d = d*d ???
what happen when d==d*d??

Edited by author 04.03.2008 17:24

it's right
if d = d * d , :)
check negative roots


what happen when d==d*d??
nothing!

I just wanted to say that we should replace d with d*d before calculations

Edited by author 04.03.2008 19:51

If I`m not mistaken, x in equation ax^2+bx+c is time from the begging...so we shouldn`t check negative roots, because it was before the start point!
What`s wrong? I can`t understand...

in this case
check == ignore

we chose smallest positive root

you can send me your code
I'll check it
in this case check != ignore :)

Please, give me some hints related to
"be careful with float point"?

use eps
for example
if (discriminant<0) continue; //   it's wrong
if (discriminant+1e-9<0) continue; //  it's right

Edited by author 06.03.2008 20:41

Thank you! I used

#define EPS 0.000000001

if(discr>=-EPS)

and had got AC!

Don't use this formula. It's not right.
Silly author mistake =)