problem with implementing this question of codechef

[lastchance]

MonkeyD wrote:

@lastchance Which both terms??

BEFORE you did the multiplying through there were two terms with Q(t) in.

The magnitude (squared) of a vector can also be written as a dot product. READ earlier posts.
|a|²=a.a

In this instance,
|Q(t) - P|²
=(Q(t) - P).(Q(t) - P)
=(Q₀+td - P).(Q₀+td - P)
=(Q₀ - P).(Q₀ - P)+2td.(Q₀ - P)+t²(d.d)
=(constant1) + t (constant2)+t²(constant3)

[badsheep]

@quirky1234
Your calculations are almost correct. Almost.
Run through a case on paper with your formulae, you'll find the error.

[closed account LA967k9E]

@badsheep I too have written code which is similar to @quirky but it passes the first test case and fails for all the case can younplease point out the error in @quirky1234 code.. I can't post my code here because it may lead to plagarism...please point out the error in @quirky1234 code ...@quirky have you found out the error in your code?

[closed account 3UohqMoL]

@lastchance just tell me only one thing about this problem i just dont get the extra multiplying factor of it

http://www.cplusplus.com/forum/beginner/238025/

[GAUjy60M]

@Wasp could you please tell the values of A,B,C.

[closed account 3UohqMoL]

I dont know man i tried a lot and always got lost in the values.What do u know about that question.

[GAUjy60M]

@badsheep please help! i have been trying this for days now :/

[GAUjy60M]

@MonkeyD @lastchance please help!!!
Has anyone been able to figure it out?
Could someone please help me to find a,b,c

[closed account 1TD80pDG]

i solved according to the formula but still not get right result ?
Find my error ? anyone ?
@lastchance

#include<iostream>
#include<math.h>
#define DB double
using namespace std;

DB dot_product_result(DB x1,DB y1, DB z1, DB x2, DB y2, DB z2)
{

    DB result1= x1*x2+y1*y2+z1*z2;

     return result1;

}


int main()
{
  DB t,p1,p2,p3,q1,q2,q3,d1,d2,d3,c1,c2,c3,r;

  cin>>t;

  while(t--)
  {     /*r^2 = |C - P|^2 - { (Q(t) - P).(C - P) }^2 / |Q(t) - P |^2*/

     cin>>p1>>p2>>p3>>q1>>q2>>q3>>d1>>d2>>d3>>c1>>c2>>c3>>r;

     cout<<p1<<p2<<p3<<q1<<q2<<q3<<d1<<d2<<d3<<c1<<c2<<c3<<r<<endl;
       
     /*|Q(t) - P|^2
=(Q(t) - P).(Q(t) - P)
=(Q0+td - P).(Q0+td - P)
=(Q0 - P).(Q0 - P)+2td.(Q0 - P)+t2(d.d)
=(constant1) + t (constant2)+t2(constant3)
*/ 
      
      
  DB constant1= dot_product_result(q1-p1,q2-p2,q3-p3,q1-p1,q2-p2,q3-p3 );
  DB constant2= dot_product_result( q1-p1,q2-p2,q3-p3,d1,d2,d3);
  DB constant3= dot_product_result(d1,d2,d3,d1,d2,d3);

      
     /* 
(Q(t) - P).(C - P)
=(Q0+td - P).(C - P)
=(Q0 - P).(C - P)+td.(C - P)
=(constant1) + t (constant2)*/ 
      
      
  DB constant1_1= dot_product_result(q1-p1,q2-p2,q3-p3,c1-p1,c2-p2,c3-p3);
  DB constant2_2= dot_product_result(d1,d2,d3,c1-p1,c2-p2,c3-p3);

      
      /*|C - P|^2 */
      
  DB term1= dot_product_result(c1-p1,c2-p2,c3-p3,c1-p1,c2-p2,c3-p3);
/*rearrange the equation and obtain the a,b,c*/

  DB a= r*r*constant3- term1*constant3+ constant2_2*constant2_2;
  DB b= r*r*constant2-term1*constant2+ 2*constant1_1*constant2_2;
  DB c= r*r*constant1- term1*constant1+constant1_1*constant1_1;

  DB time1= -b/2*a+( sqrt(b*b-4*a*c) )/2*a;

  DB time2= -b/2*a-( sqrt(b*b-4*a*c) )/2*a;

  DB time;
  if(time1<time2)
  time=time1;
  else
  time= time2;


  cout<<time1<<" "<<time2<<endl;
  cout<<time<<endl;



  }


}

[quirky1234]

@ipg_2016069 You have not considered the case when a=0. In that case, the answer will be t=(-c/b) because quadratic equation in terms of t has become a linear equation in terms of t. Bee-tee-dubs, your code is fine as far as I think.

[codexhammer]

Unable to find error but even after considering the case a=0 it gives incorrect time value. So there's something wrong with the formula you are using.

[closed account 1TD80pDG]

still not get expected result . i think may be formula is misleading or something i don't know ? plz find any error ? only first test case is okay, all other test case gives wrong answer . anyone provide me other test cases ?
@lastchance

#include<iostream>
#include<math.h>
#define DB double
using namespace std;

DB dot_product_result(DB x1,DB y1, DB z1, DB x2, DB y2, DB z2)
{

    DB result1= x1*x2+y1*y2+z1*z2;

     return result1;

}


int main()
{
  DB t,p1,p2,p3,q1,q2,q3,d1,d2,d3,c1,c2,c3,r;

  cin>>t;

  while(t--)
  {     /*r^2 = |C - P|^2 - { (Q(t) - P).(C - P) }^2 / |Q(t) - P |^2*/

     cin>>p1>>p2>>p3>>q1>>q2>>q3>>d1>>d2>>d3>>c1>>c2>>c3>>r;

     //cout<<p1<<p2<<p3<<q1<<q2<<q3<<d1<<d2<<d3<<c1<<c2<<c3<<r<<endl;
       
     /*|Q(t) - P|^2
=(Q(t) - P).(Q(t) - P)
=(Q0+td - P).(Q0+td - P)
=(Q0 - P).(Q0 - P)+2td.(Q0 - P)+t2(d.d)
=(constant1) + t (constant2)+t2(constant3)
*/ 
      
      
  DB constant1= dot_product_result(q1-p1,q2-p2,q3-p3,q1-p1,q2-p2,q3-p3 );
  DB constant2= 2*dot_product_result( q1-p1,q2-p2,q3-p3,d1,d2,d3);
  DB constant3= dot_product_result(d1,d2,d3,d1,d2,d3);

      //cout<<constant1<<" "<<constant2<<" "<<constant3<<endl;
     /* 
(Q(t) - P).(C - P)
=(Q0+td - P).(C - P)
=(Q0 - P).(C - P)+td.(C - P)
=(constant1) + t (constant2)*/ 
      
      
  DB constant1_1= dot_product_result(q1-p1,q2-p2,q3-p3,c1-p1,c2-p2,c3-p3);
  DB constant2_2= dot_product_result(d1,d2,d3,c1-p1,c2-p2,c3-p3);

      //cout<<constant1_1<<" "<<constant2_2<<endl;
      /*|C - P|^2 */
      
  DB term1= dot_product_result(c1-p1,c2-p2,c3-p3,c1-p1,c2-p2,c3-p3);
/*rearrange the equation and obtain the a,b,c*/
      
      //cout<<term1<<endl;

  DB a= r*r*constant3- term1*constant3+ constant2_2*constant2_2;
  DB b= r*r*constant2-term1*constant2+ 2*constant1_1*constant2_2;
  DB c= r*r*constant1- term1*constant1+constant1_1*constant1_1;

      
     // cout<<a<<" "<<b<<" "<<c<<endl;
    
   if(a==0)
       cout<<-c/b<<endl;
   else {   
      
  DB time1= -b/2*a+( sqrt(b*b-4*a*c) )/2*a;

  DB time2= -b/2*a-( sqrt(b*b-4*a*c) )/2*a;

  DB time;
  if(time1<time2)
  time=time1;
  else
  time= time2;


  //cout<<time1<<" "<<time2<<endl;
  cout<<time<<endl;

   }

  }


}

[iGEqDjzh]

@quirky1234 Did you find out what was wrong in your formulae. I am getting the exact same formulae as yours. Please help !

[MikeyBoy]

Please stop pestering users with the same questions over and over. People will help when they can. Spamming multiple posts asking the same thing over and over is rude, annoying, and may well cause you to be reported and banned.

[keskiverto]

ipg 2016069 wrote:

i think may be formula is misleading or something i don't know ? plz find any error ?

lastchance wrote:

Having long coordinate expansions just attracts bugs and makes code indecipherable.

That means that one should not implement
// constant1 = (Q0 - P).(Q0 - P)
with
DB constant1 = dot_product_result(q1-p1,q2-p2,q3-p3,q1-p1,q2-p2,q3-p3 );
but write, given

vec3 Q0;
vec3 P;
std::cin >> Q0 >> P;
auto dot = [](const vec3& v){ return dot(v, v);};

auto constant1 = dot(Q0 - P); // this looks like math, doesn't it? 

What is your actual equation? Is it this?
r^2 = |C - P|^2 - { (Q(t) - P).(C - P) }^2 / |Q(t) - P |^2

You did already work out that |C - P|^2 = dot(C-P)
and (Q(t) - P).(C - P) = dot(Q0 - P, C - P) + t * dot(d, C - P)

Lets substitute the first, and substitute the |Q(t) - P |^2 with X:
r^2 = dot(C-P) - { (Q(t) - P).(C - P) }^2 / X

Did you multiply both sides with X? You want to:
r^2 * X = dot(C-P) * X - { (Q(t) - P).(C - P) }^2 / X * X
Which simplifies to:
r^2 * X = dot(C-P) * X - { (Q(t) - P).(C - P) }^2
Lets convert the (Q(t) - P).(C - P) too:

r*r*X = dot(C-P) * X
    - { dot(Q0-P, C-P) + t*dot(d, C-P) }^2

and expand the X into dot(Q0-P) + t*2*dot(d, Q0-P) + t*t*dot(d):

r*r* (dot(Q0-P) + t*2*dot(d, Q0-P) + t*t*dot(d))
   = dot(C-P) * (dot(Q0-P) + t*2*dot(d, Q0-P) + t*t*dot(d))
     - (dot(Q0-P, C-P) + t*dot(d, C-P))*(dot(Q0-P, C-P) + t*dot(d, C-P))

Little bit more rearranging and that equation will both resemble
0 = t*t*A + t*B + C
and be compilable code.


That is what you did in the

/*rearrange the equation and obtain the a,b,c*/

didn't you?

[codexhammer]

@keskiverto
r^2 = |C - P|^2 - { (Q(t) - P).(C - P) }^2 / |Q(t) - P |^2
I guess this isn't the right equation. On simplifying it all the terms on the right hand side of the equations cancel each other. This is the correct equation i guess:
r^2 = {|C - P|^2 - { (Q(t) - P).(C - P) }^2} / |Q(t) - P |^2

Or am i terribly wrong. But the first equation which you said, gives A = square(direction_vector) which is in no way zero for the given sample case.

This is what I have implemented. I followed the solution at https://math.stackexchange.com/questions/2805113/line-touching-a-sphere and implemented taking the direction vector. Gives correct for the given test case but wrong for rest.

def dot(a,b):
    r = a[0]*b[0] + a[1]*b[1] + a[2]*b[2]
    return r
for _ in range(int(input())):
    x1,y1,z1,x2,y2,z2,d1,d2,d3,c1,c2,c3,r = map(float,input().split())
    a = x2-x1
    b = y2-y1
    c = z2-z1
    k = x1-c1
    l = y1-c2
    m = z1-c3
    term1 = (r**2)*(d1**2) + (r**2)*(d2**2) + (r**2)*(d3**2)
    term2 = (d1*l - d2*k)**2 + (d2*m - d3*l)**2 + (d3*k - d1*m)**2
    A = term1 - term2
    term11 = 2*(r**2)*(a*d1 + b*d2 + c*d3)
    term22 = 2*((a*l-b*k)*(d1*l-d2*k) + (b*m-c*l)*(d2*m-d3*l) + (c*k-a*m)*(d3*k-d1*m))
    B = term11-term22
    ter1 = (r**2)*(a**2 + b**2 + c**2)
    ter2 = (a*l-b*k)**2 + (b*m-c*l)**2 + (c*k-a*m)**2
    C = ter1-ter2
    print(A,B,C)
    if A==0:
        t = -1*C/B
        print(t)
        continue
    else:
        t1 = (-1*B + (B**2 - 4*A*C)**0.5)/2*A
        t2 = (-1*B - (B**2 - 4*A*C)**0.5)/2*A
        t=0
        if t1<0:
            t=t2
        elif t2<0:
            t=t1
        elif t1>=0 and t2>=0:
            t=min(t1,t2)
        print(t)

The code is in python but is easily comprehensible.

[iGEqDjzh]

@ipg 2016069 Your formula for one of the term is not correct, you are very close. Just do the calculations once more you will definitely find the error!

[keskiverto]

I don't claim that to be the correct equation. It was in ipg's code, so I did play with it.

http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
has essentially

r^2 = {|PC|^2 * |QC|^2 - (PC.QP)^2} / |QP|^2
where
PC = P - C
QC = Q0 - C + td
QP = Q0 - P + td

which seems different from the previous equations.


One can start with wrong equation.
One can make mistakes, while rearraging the equation.
One can fail to convert the equation into code.

[DGLCfSEw]

@iamrahul I have also coded similar to ipg, and am also passing only the first subtask, I can't find the error, Is the equation correct?

can you just tell a sample test case may be, so we can analyze properly?

[closed account 3UohqMoL]

Hi all i got 25 points but not yet passing the next task of 75 points i.e 3d equation