ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1600. Airport

could anyone give some tests?
Posted by Faeton (Kyiv - Mohyla Academy) 2 Mar 2008 22:20
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
Re: could anyone give some tests?
Posted by KIRILL(ArcSTUpid coder:) 3 Mar 2008 04:34
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
Re: could anyone give some tests?
Posted by Anastas 3 Mar 2008 20:16
Please give me tests when the roots are negative!!
Re: could anyone give some tests?
Posted by KIRILL(ArcSTUpid coder:) 3 Mar 2008 22:32
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
Re: could anyone give some tests?
Posted by SuperLight 3 Mar 2008 23:24

Edited by author 03.03.2008 23:43

Edited by author 03.03.2008 23:43
Re: could anyone give some tests?
Posted by SuperLight 4 Mar 2008 14:46
Why we should check negative roots if d = d*d ???
what happen when d==d*d??

Edited by author 04.03.2008 17:24
Re: could anyone give some tests?
Posted by KIRILL(ArcSTUpid coder:) 4 Mar 2008 19:46
SuperLight wrote 4 March 2008 14:46
Why we should check negative roots if 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
Re: could anyone give some tests?
Posted by SuperLight 4 Mar 2008 22:33
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...
Re: could anyone give some tests?
Posted by KIRILL(ArcSTUpid coder:) 5 Mar 2008 02:30
SuperLight wrote 4 March 2008 22:33
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 :)
Re: could anyone give some tests?
Posted by Beksinski 6 Mar 2008 13:50
Please, give me some hints related to
"be careful with float point"?
Re: could anyone give some tests?
Posted by KIRILL(ArcSTUpid coder:) 6 Mar 2008 20:40
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
Re: could anyone give some tests?
Posted by Beksinski 10 Mar 2008 00:25
Thank you! I used

#define EPS 0.000000001

if(discr>=-EPS)

Re: could anyone give some tests?
Posted by unlucky [Vologda SPU] 8 Nov 2009 00:10
Faeton (Kyiv - Mohyla Academy) wrote 2 March 2008 22:20
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
Don't use this formula. It's not right.
Silly author mistake =)