problem with implementing this question of codechef

[qwerty1qwerty]

@lastchance
can you help me in solving this question
link to the question-:
https://www.codechef.com/JUNE18B/problems/VSN

[keskiverto]

Help? In what part of it?


The Q should become visible to P, when the "line-of-sight" (from P to Q) is a tangent of the sphere.

You have a line that crosses P and Q(t).
You know that distance from that line to c is r.
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

[qwerty1qwerty]

@keskiverto
can you provide a code of this question

[keskiverto]

I will not. Nobody should. It is your task to think and write.

We can at most explain the errors in your code.

[closed account 3UohqMoL]

What formula we have to use??

[dhayden]

This is a math problem. Figure out how to do one of these by hand. Once you have the math, commit it to code.

[lastchance]

qwerty1qwerty wrote:

@lastchance
can you help me in solving this question

I think it's probably time you gave those little grey cells a workout!

wasp wrote:

What formula we have to use??

See
http://www.cplusplus.com/forum/beginner/237933/#msg1062239

But same comment as above!

[closed account 1TD80pDG]

from the point Q0 (x2,y2,z2) and its direction ratio is given then we find the 3D line-1 and we have another side of Sphere point is P0 (x1,y1,z1) and let's assume its tangents and line-1 crossing point is X, Y, Z. then we find the tangent's equation by these two points(X,Y, Z) and (x1,y1,z1). and distance from the center to this tangents is radius (r). above these, we can find the point X, Y, Z and then how can we calculate the time? we can find the distance between Q(0) (x2,y2,z2) and Q(t) (X,Y,Z). but there is not velocity is given? what I'm missing here. can anyone tell me? can anyone have the better approach

[Repeater]

but there is not velocity is given?

Velocity is given. It's called d in the original text.

[closed account 1TD80pDG]

I want to do subtask but it gives me the wrong answer except for the first test case

for 2D I'm assume is that x3=y3=zc=d3=0;

first, I find the Gradient m1 and m2 for tangent from the point P(x1,y1,z1) for the circle (xc,yc,zc) and radius r. then I obtain two lines and solve these lines with Q(0)-Q(t) line and get the two-points of intersection and find the distance between the intersection points(X1, Y1, Z1) and Q0(x2,y2,2) and point(X2,Y2,Z2) and Q0(x2,y2,z2) and then divided these distance by direction cosine value and get the value of time for m1(one intersection point) and m2(second intersection point) because we have two tangents and then compare both time and minimum is our answer. but is giving the wrong answer. can any tell me where I'm lacking in this problem?

#include <iostream>
#include <math.h>
using namespace std;
int main() {



int t;
    cin>>t;
    while(t--){

 long long  x1,y1,z1;
 long long x2,y2,z2;
 long long d1,d2,d3;
 long long xc,yc,zc;
 long long r;
   
    cin>>x1>>y1>>z1;
    cin>>x2>>y2>>z2;
    cin>>d1>>d2>>d3;
    cin>>xc>>yc>>zc;
    cin>>r;
    
    
    
    

 long long a_m=r*r-xc*xc+2*x1*xc-x1*x1;

 long long b_m= 2*yc*xc-2*xc*y1+2*x1*y1-2*x1*yc;

 long long c_m= r*r-y1*y1-yc*yc+2*y1*yc;

 long long m1=  -b_m/2*a_m + sqrt(b_m*b_m- 4*a_m*c_m )/2*a_m;

 long long m2=  -b_m/2*a_m - sqrt(b_m*b_m- 4*a_m*c_m )/2*a_m;



 long long X1=  (d2/(d2-d1*m1))*( (d1/d2)*(y1-m1*x1-y2 )+ x2 );

 long long Y1= m1*X1+y1-m1*x1;

 long long X2=  (d2/(d2-d1*m2))*( (d1/d2)*(y1-m2*x1-y2 )+ x2 );

 long long Y2= m2*X2+y1-m2*x1;


//cout<<X1<<" "<<Y1<<endl;
    //cout<<X2<<" "<<Y2<<endl;
    
   long long distance1= sqrt( (X1-x2)*(X1-x2) + (Y1-y2)*(Y1-y2) )  ;
    
     long long  distance2= sqrt( (X2-x2)*(X2-x2) + (Y2-y2)*(Y2-y2) )  ;

 long long distance=0;
    
    if(distance1>= distance2)
        distance=distance2;
    else
        distance=distance1;
    
    
    //cout<<distance;

     long long velocity= sqrt(d1*d1+d2*d2+d3*d3);
    
     long long time= (distance)/(velocity);
    cout<<time<<endl;
    

    }
}

[lastchance]

You won't be solving an intersection problem like this in integers (which is what long long variables are).

You need doubles.

Your method wouldn't generalise to 3-d either. You should start thinking about vectors from the word go.

[helios]

The problem can be reduced to 2D coordinates, actually. But you have to give up Q moving with constant velocity. The curve Q(t) R->R^2 is seriously non-trivial, particularly compared to R->R^3. The upside is that you only have to check if Q is within a circular region around origin.

[closed account 1TD80pDG]

can anyone provide me sample test cases for this problems. I find the Q(t) point let say (X,Y,Z) and Q(0) is already have let say Q(0) (x2,y2,z2). and direction cosine is d1,d2,d3. then required time is distance between Q(0) and Q(t) divided by velocity= sqrt(d1*d1+d2*d2+d3*d3) . is it correct ?

[lastchance]

IF you can find Q(t) then at the point of intersection then that would be true. It is feasible in 2-d because there are only 2 lines tangent from P to the circle. It is not so trivial in 3-d because there are an infinity of lines tangential from P to the sphere.

You may find it easier to note that t is just a parameter on the vector equation of a line and find t directly. In most cases there will be 2 solutions, hence a quadratic for t. From the question stated, one of these will be in negative time and not needed. Occasionally, if P is close to the sphere there will be only one solution. This is, in fact, the case in the codechef example given, WHICH YOU COULD USE AS AN EXAMPLE. You can easily make up your own examples in 2-d.

Your code won't work as intended if the variables are all integers.

TBH, you never need to explicitly find a distance anywhere, it is irrelevant that d is a velocity, and you simply have to solve for t, a parameter of a line.

[closed account 3UohqMoL]

Hi. Can i write Q(t) = Q(0) + t(d)
and we need to find parameter t in it.

So, in this we can equate distance of P from the Sphere and Q from the sphere.This gives 1 answer correct but not sure for others.

[closed account 3UohqMoL]

@ipg required time is not the distance between Q(0) and Q(t) . I thing time might be the parameter of Q(t). Q(t) is the point at which both the Tangents from P and Q intersect.
And their Distance with the center is radius

[lastchance]

@Wasp, your geometry is seriously flawed. Draw a proper diagram.

[keskiverto]

ipg wrote:

required time is distance between Q(0) and Q(t) divided by velocity

Yes.

http://onlinemschool.com/math/library/vector/length/
Lets call Q(t) - Q(0) vector q. The q has length |q|
The q == t*d by task definition and thus |q| == t*|d|
We assume that 0 < |d| (or was the task text explicit about it?)
Therefore t == |q| / |d|

Lets assume that there is a function F(A,B,X) that takes three points as arguments and computes the distance between point X and the line that goes through A and B. Plugging in the real values:
r == F( P, Q+t*d, c )
Where the t is the only unknown.


You could start by defining (or fetching) a struct/class for 3D point/vector that has necessary members so that you can focus syntactically on the math.

[closed account 3UohqMoL]

@keskiverto we have a parameter t while calculating Q(t). Also, we have to calculate distance between centre and line joining P and Q(t). So, is this parameter same in both the cases??

[closed account 3UohqMoL]

@lastchance and @keskiverto thanks i think i got that.

r² = |C - P|² - | (Q_t - P).(C - P) / (Q_t - P) |²

Please tell me if am right.
Also guide me on how can i code this to solve 2 degree equation in t.