10794 - The Deadly Olympic Returns!!!

[arif_pasha]

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.

[Adrian Kuegel]

Check if you will maybe divide by zero somewhere in your program for some inputs.

[arif_pasha]

Thanks Adrian, I overlooked that. Changed that and got AC

[Nemo]

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.

[Martin Macko]

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.

Make sure you don't divide ints, but doubles.

[Nemo]

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........

[Martin Macko]

...that it doesn't automaticallly convert to the larger type!??!?

How could the compiler possibly know you want to convert it to double or you want an integer division?

May try to retype one of the operands:

Code: Select all

int a,b;
double c=(double)a/b;

[rieo]

hi, i have the same problem, and i don't know where is wrong

can anyone post some I/O ?

thx.

[Martin Macko]

hi, i have the same problem, and i don't know where is wrong
can anyone post some I/O ?
thx.

Some random inptus:

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

My AC's outputs:

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

[rieo]

thx martin, i have the same answer with you.
it seems my formula is right, too.
if a=0 then T=0, else T= -b/2a
if T<0 then T=0.
I store all input use double.... but still WA..

[Martin Macko]

thx martin, i have the same answer with you.
it seems my formula is right, too.
if a=0 then T=0, else T= -b/2a
if T<0 then T=0.
I store all input use double.... but still WA..

If nothing helps, you can post your code here. Maybe, I'll have time to find the bug in it.

[rieo]

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=(x2-x1)/time;
    v1.y=(y2-y1)/time;
    v1.z=(z2-z1)/time;
    scanf ("%lf %lf %lf %lf %lf %lf", &x3, &y3, &z3, &x4, &y4, &z4);
    v2.x=(x4-x3)/time;
    v2.y=(y4-y3)/time;
    v2.z=(z4-z3)/time;

    a=(v2.x-v1.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v2.y-v1.y)+(v2.z-v1.z)*(v2.z-v1.z);
    b=2*((x1*v1.x+x3*v2.x-x3*v1.x-x1*v2.x)+(y1*v1.y+y3*v2.y-y3*v1.y-y1*v2.y)+(z1*v1.z+z3*v2.z-z3*v1.z-z1*v2.z));
    c=(x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)+(z3-z1)*(z3-z1);

    (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]

if someone finds the bug, i will be very grateful. thx

Try this one:

Code: Select all

1
7146
-6629 514 6882 -1215 -1840 7289
5174 -6242 7051 -4736 2360 5809

My AC's output:

Code: Select all

Case 1: 1702.0136

Your output:

Code: Select all

Case 1: 1702.0137

[rieo]

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)

[max_zd]

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.