10794  The Deadly Olympic Returns!!!
Moderator: Board moderators

 New poster
 Posts: 42
 Joined: Fri Jun 13, 2003 3:47 pm
 Location: Dhaka , Bangladesh
 Contact:
10794  The Deadly Olympic Returns!!!
i tried to solved this problem, but gettin WA . My algo is
described below
[algo]
first i have calculated the velocity vectors: v1<x,y,z> and
v2<x,y,z> by the following rule
x2 = x1 + v1.x * time;
y2 = y1 + v1.y * time;
z2 = z1 + v1.z * time;
and v2<x,y,z> calculated in the same fashion.
let 1st missile comes to point p<x,y,z> after
time 't' and 2nd missile to point q<x,y,z>.
then i get
p.x = x1 + v1.x * t;
p.y = y1 + v1.y * t;
p.z = z1 + v1.z * t;
where <x1,y1,z1> is the initial position of 1st missile.
and
q.x = x3 + v2.x * t;
q.y = y3 + v2.y * t;
q.z = z3 + v2.z * t;
<x3,y3,z3> is the initial position of 2nd missile.
then i got the equation of the distance between p and q which
is: sqrt[ a second order equation of t, say at^2+bt+c ]
then i calculated the turning point(time) of this equation and say
that time was T [ T = b/2a ]. i just checked if T<0 then the initial
distance is the minimum or the min value is sqrt(aT^2+bT+c).
is there anything wrong with my algo or i just missed some point?
can anybody help me? Thanks in advance.
described below
[algo]
first i have calculated the velocity vectors: v1<x,y,z> and
v2<x,y,z> by the following rule
x2 = x1 + v1.x * time;
y2 = y1 + v1.y * time;
z2 = z1 + v1.z * time;
and v2<x,y,z> calculated in the same fashion.
let 1st missile comes to point p<x,y,z> after
time 't' and 2nd missile to point q<x,y,z>.
then i get
p.x = x1 + v1.x * t;
p.y = y1 + v1.y * t;
p.z = z1 + v1.z * t;
where <x1,y1,z1> is the initial position of 1st missile.
and
q.x = x3 + v2.x * t;
q.y = y3 + v2.y * t;
q.z = z3 + v2.z * t;
<x3,y3,z3> is the initial position of 2nd missile.
then i got the equation of the distance between p and q which
is: sqrt[ a second order equation of t, say at^2+bt+c ]
then i calculated the turning point(time) of this equation and say
that time was T [ T = b/2a ]. i just checked if T<0 then the initial
distance is the minimum or the min value is sqrt(aT^2+bT+c).
is there anything wrong with my algo or i just missed some point?
can anybody help me? Thanks in advance.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 New poster
 Posts: 42
 Joined: Fri Jun 13, 2003 3:47 pm
 Location: Dhaka , Bangladesh
 Contact:
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: 10794
Make sure you don't divide ints, but doubles.Nemo wrote:my algo is same. checked div by 0. but still WA. can anybody give me some sample critical I/O? another thing....am i supposed to truncate the output or simply round it up? i used int for input and double for calculation.
Sorry for late reply
Thank you. You were right. I was doing an integer division and storing it in a double.
But I wonder how I forgot (or did I ever know it?) that it doesn't automaticallly
convert to the larger type!??!?
ummmm............a bit late reply heh heh.....i was very busy........
But I wonder how I forgot (or did I ever know it?) that it doesn't automaticallly
convert to the larger type!??!?
ummmm............a bit late reply heh heh.....i was very busy........
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: Sorry for late reply
How could the compiler possibly know you want to convert it to double or you want an integer division?Nemo wrote:...that it doesn't automaticallly convert to the larger type!??!?
May try to retype one of the operands:
Code: Select all
int a,b;
double c=(double)a/b;
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Some random inptus:rieo wrote:hi, i have the same problem, and i don't know where is wrong
can anyone post some I/O ?
thx.
Code: Select all
15
9830
7348 6866 3235 8617 9548 4314
9093 3523 7015 2139 7555 3625
323
1197 2307 9986 9087 5622 9550
7303 8550 3038 5416 7393 7218
738
3428 8668 6807 9807 94 992
4465 8470 4846 3578 7087 4394
3707
2602 9953 2791 6384 5793 9348
4194 3009 8068 2767 7105 3691
7373
9337 5549 9802 6144 8679 3753
4848 2108 5943 1029 2301 3963
2430
6349 6635 1136 8113 3208 7557
8764 9394 3424 332 4038 783
1492
5369 5050 1768 5172 8319 5465
8581 10 944 7362 3866 376
1483
4939 4427 9742 3924 9010 772
2605 5359 8434 9181 3472 6254
9180
9285 8936 8790 1053 9327 9849
5440 4696 3771 3616 9103 5576
9141
481 6008 3343 223 1232 8267
2023 3828 6160 8514 8780 1822
7744
8598 7740 7203 1220 5583 950
1370 6159 114 1373 4893 9531
846
6062 5797 1575 595 210 7959
7834 9729 5005 646 8478 5209
7860
1572 7531 5427 6658 8622 3942
4291 7220 4826 5822 4973 9243
9374
7434 2681 6397 4140 7515 4975
2100 425 9744 1877 8 45
882
3893 2913 2174 8466 7439 8472
5475 7984 9059 378 8674 1465
Code: Select all
Case 1: 6257.1515
Case 2: 2534.2693
Case 3: 2388.3530
Case 4: 4135.5045
Case 5: 9299.2722
Case 6: 5842.8995
Case 7: 6186.2852
Case 8: 5458.2166
Case 9: 6687.1276
Case 10: 3344.6994
Case 11: 8215.3767
Case 12: 13536.4392
Case 13: 12525.3050
Case 14: 6171.8921
Case 15: 11999.2161
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
if someone finds the bug, i will be very grateful. thx
Code: Select all
#include <stdio.h>
#include <math.h>
typedef struct {
double x, y, z;
} velocity;
int main()
{
int test_case, data=0, time;
double x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4;
double a, b, c, t, dis;
velocity v1, v2;
scanf ("%d", &test_case);
while (test_case) {
scanf ("%d", &time);
scanf ("%lf %lf %lf %lf %lf %lf", &x1, &y1, &z1, &x2, &y2, &z2);
v1.x=(x2x1)/time;
v1.y=(y2y1)/time;
v1.z=(z2z1)/time;
scanf ("%lf %lf %lf %lf %lf %lf", &x3, &y3, &z3, &x4, &y4, &z4);
v2.x=(x4x3)/time;
v2.y=(y4y3)/time;
v2.z=(z4z3)/time;
a=(v2.xv1.x)*(v2.xv1.x)+(v2.yv1.y)*(v2.yv1.y)+(v2.zv1.z)*(v2.zv1.z);
b=2*((x1*v1.x+x3*v2.xx3*v1.xx1*v2.x)+(y1*v1.y+y3*v2.yy3*v1.yy1*v2.y)+(z1*v1.z+z3*v2.zz3*v1.zz1*v2.z));
c=(x3x1)*(x3x1)+(y3y1)*(y3y1)+(z3z1)*(z3z1);
(a==0) ? (t=0) : (t=b/(2*a));
if (t<0)
t=0;
dis=sqrt(a*t*t+b*t+c);
printf ("Case %d: %.4lf\n", ++data, dis);
}
return 0;
}
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Try this one:rieo wrote:if someone finds the bug, i will be very grateful. thx
Code: Select all
1
7146
6629 514 6882 1215 1840 7289
5174 6242 7051 4736 2360 5809
Code: Select all
Case 1: 1702.0136
Code: Select all
Case 1: 1702.0137
finally, i got acc... the problem is not the precision error...
if distance=sqrt(a*t*t+b*t+c) a.b.c as above
the minimum distance should be sqrt( a(t+b/2a)^2 + ...)
then we consider if a=0 or not,
if a!=0 then choose t=b/2a
else a==0, it means v1_x==v2_x and v1_y==v2_y and v1_z==v2_z, so b==0, too... so dis=sqrt(c)
if t<0 then let t=0
which case i don't consider is..
there is one possible.. t>0 but a*t*t+b*t+c <0.. , so in this case distance must be 0, not sqrt(a*t*t+b*t+c)
if distance=sqrt(a*t*t+b*t+c) a.b.c as above
the minimum distance should be sqrt( a(t+b/2a)^2 + ...)
then we consider if a=0 or not,
if a!=0 then choose t=b/2a
else a==0, it means v1_x==v2_x and v1_y==v2_y and v1_z==v2_z, so b==0, too... so dis=sqrt(c)
if t<0 then let t=0
which case i don't consider is..
there is one possible.. t>0 but a*t*t+b*t+c <0.. , so in this case distance must be 0, not sqrt(a*t*t+b*t+c)
Re: 10794  The Deadly Olympic Returns!!!
Just as reio said, the problem is that. But I don't know when will this situation happen? I think that quadraic function will never be negative.