10794 - The Deadly Olympic Returns!!!

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

10794 - The Deadly Olympic Returns!!!

Post by arif_pasha » Fri Jan 14, 2005 10:02 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Jan 14, 2005 11:19 pm

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

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Sat Jan 15, 2005 8:04 am

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

Nemo
New poster
Posts: 16
Joined: Thu Apr 14, 2005 10:40 am

10794

Post by Nemo » Fri Jul 29, 2005 11:01 am

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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10794

Post by Martin Macko » Fri Jul 29, 2005 4:22 pm

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.
Make sure you don't divide ints, but doubles.

Nemo
New poster
Posts: 16
Joined: Thu Apr 14, 2005 10:40 am

Sorry for late reply

Post by Nemo » Mon Aug 15, 2005 6:24 pm

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

User avatar
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

Post by Martin Macko » Tue Aug 16, 2005 9:05 am

Nemo wrote:...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
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain

Post by rieo » Wed Aug 16, 2006 6:47 pm

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

can anyone post some I/O ?

thx.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Wed Aug 16, 2006 10:16 pm

rieo wrote: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
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain

Post by rieo » Thu Aug 17, 2006 7:23 am

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Thu Aug 17, 2006 2:57 pm

rieo wrote: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.. :cry:
If nothing helps, you can post your code here. Maybe, I'll have time to find the bug in it.

rieo
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain

Post by rieo » Thu Aug 17, 2006 6:35 pm

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;
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Wed Aug 23, 2006 7:39 pm

rieo wrote: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
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain

Post by rieo » Mon Oct 02, 2006 8:22 am

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
New poster
Posts: 2
Joined: Tue Apr 10, 2007 2:51 pm

Re: 10794 - The Deadly Olympic Returns!!!

Post by max_zd » Mon Apr 14, 2008 4:47 am

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.

Post Reply

Return to “Volume 107 (10700-10799)”