problem with implementing this question of codechef

[DGLCfSEw]

@lastchance

The equation is slightly more accurately written
r2 = |C - P|2 - { (Q(t) - P).(C - P) }2 / |Q(t) - P |2
or
r2 = { mag(C - P) }2 - { dotProduct( Q(t) - P, C - P ) }2 / { mag( Q(t) - P ) }2

You need to multiply the whole lot through by |Q(t) - P |2 and write Q(t) = Q0+td. After multiplying out you will get a quadratic in t.

I tried to implement this on paper first. But, still am getting wrong ans. Please guide me

So, I used the property of dot product of two vector a.b as (ax*bx+ay*by):

the coordinates of Q,C and P are represented as qx,qy,qz and cx,cy,cz and so on.

Let a=qx-px,b=qy-py,c=qz-pz,d=cx-px,e=cy-py and f=cz-pz:

cooeficients of quadratic eq of t:

A=pow(dx*r,2)+pow(dy*r,2)+pow(dz*r,2)+pow(dx*d,2)+pow(dy*e,2)+pow(dz*f,2);
B=2*(a*dx*pow(r,2)+pow(r,2)*b*dy+pow(r,2)*c*dz+a*dx*pow(d,2)+b*dy*pow(e,2)+c*dz*pow(f,2));
C=pow(a*r,2)+pow(b*r,2)+pow(c*r,2)-pow(d,2)-pow(e,2)-pow(f,2)+pow(a*d,2)+pow(b*e,2)+pow(c*f,2);

Please point out the wrong calculation.

[lastchance]

It would be shorter to point out which is the correct calculation, @MonkeyD! It is ...

[DGLCfSEw]

But it's giving me wrong answer even for sample test case...

[closed account 3UohqMoL]

Hello everyone, I have got the equation.But, it gave me only the test case answer correct.
@lastchance can you help me please ?

A = C_xQ_y - C_xP_y - P_xQ_y - C_yQ_x + C_yP_x + P_yQ_x

B = C_xD_y - P_xD_y - C_yD_x + P_yD_x

P = (Q_x - P_x)² + (Q_y - P_y)²

Q = D_x² + D_y²

X = 2(Q_xD_x - P_xD_x + Q_yD_y - P_yD_y)

|PC ✖ PQ| = A + Bt
|PQ| = sqrt(P + Qt² + Xt)

The Quadratic equation is :

t²(R²Q - B²) + t(R²X - 2AB) + (R²P - A²)

Here's my code that passed first subtask

  

#include <bits/stdc++.h>
using namespace std;

typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test;
    ld px, py, pz;
    ld qx, qy, qz;
    ld dx, dy, dz;
    ld cx, cy, cz;
    ld r;
    cin >> test;
    cout.setf(ios::fixed);
    while (test--) {
        cin >> px >> py >> pz;
        cin >> qx >> qy >> qz;
        cin >> dx >> dy >> dz;
        cin >> cx >> cy >> cz;
        cin >> r;
        ld a = (cx * qy) - (cx * py) - (px * qy) - (cy * qx) + (cy * px) + (py * qx);
        ld b = (cx * dy) - (px * dy) - (cy * dx) + (py * dx);
        ld p = (qx - px)*(qx - px) + (qy - py)*(qy - py);
        ld q = (dx * dx) + (dy * dy);
        ld x = 2 * ((qx * dx) - (px * dx) + (qy * dy) - (py * dy));
        ld a1 = (r * r * q)- (b * b);
        ld a2 = (r * r * x) - (2 * a * b);
        ld a3 = (r * r * p) - (a * a);
        if (a1 == 0.0) {
            cout << (-a3) / a2 << endl;
        } else {
            ld t1 = (-a2 + sqrt((a2 * a2) - (4 * a1 * a3))) / (2 * a1);
            ld t2 = (-a2 - sqrt((a2 * a2) - (4 * a1 * a3))) / (2 * a1);
            if (t1 > t2) {
                cout << t1 << endl;
            } else {
                cout << t2 << endl;
            }
        }
        return 0;
    }
} 

[DGLCfSEw]

@Wasp are you only doing for 2D ??

[MrHacker]

I am first trying to solve subtask#1 ,i am trying to find the variable t by using the formula of perpendicular distance between a point and line .here the line equation is obtained from P,Q using two point form and the point will be centre with perpendicular distance as radius.
if the line equation is Ax+By+C=0 and the point is(Px,Py) then the formula is

perpendicular distance=|APx+BPy+C|/sqrt(A^2+B^2)

is this approach correct for the subtask 1 that is only for 2d?

can anyone help me out:)

[closed account 3UohqMoL]

@monkeyD yes i am trying first for only 2-D.But my code works on the sample case

[DGLCfSEw]

@lastchance if my calculations are correct then the sample case doesn't give A as 0. So, Please tell me where did I go wrong in calculating the coefficients.

[lastchance]

@MonkeyD,
Your calculations are NOT correct. You missed the irony: I was trying to write "blank space".

Go back through the thread and read some of the comments. Note in particular mine that you should use vector notation (like dot products) as long as possible, not write out huge component-by-component expansions - and also @keskiverto's that you can very conveniently carry this over to code.

In fact my code structure is almost exactly that suggested by @keskiverto: my individual components are stored in a struct (similar to a class) and about the only difference is that I also overload the stream >> operator as well for convenience. My int main() contains NO individual components of vectors: all of these are hidden within a dot() function and the overloaded minus (-) and stream >> operators (where they are simple and mercifully short).

I'm not going to even attempt to check long coordinate expansions, although I can see yours is wrong from the word go as it wouldn't allow A to be zero. You would also help yourself and others by using sensible names for variables, not a, b, c, d, e, f. Familiarise yourself with vector geometry and simplify both your mathematics and your code.

[DGLCfSEw]

@lastchance

Note in particular mine that you should use vector notation (like dot products) as long as possible, not write out huge component-by-component expansions

But Q(t) is in the dot product. So, if we want the quadratic expression in terms of t, we have to get it out of the dot product, don't you think so??
That is why I used dotproduct(Q(t)-P,C-P) as x part of(Q(t)-P) * x part of (C-P) amd same for y and z and then sum of all three coordinates.

Last time I missed a bracket, now solving it, the dotproduct just ended up getting canceled out by some part of the first term in RHS*denominator.

Am I going in the wrong direction ?

[closed account 3UohqMoL]

@lastchance my code works for 1 case and not for other 2 can u provide me a reason for that about whats
Going wrong in that code

[closed account j8MNvCM9]

If someone gets anything completely correct,then please share the formula/code here.

[lastchance]

@Wasp
I appreciate your use of |PC ✖ PQ|, which suggests that you have indeed been studying my diagram. However, the vector product is only here because of the sine of the angle and is relatively complicated to use when you only need its magnitude. You will find it easier to replace the square of its magnitude using the identity
|a ✖ b|² = |a|²|b|²-(a.b)²
which comes immediately from the (geometric) definition of dot and cross products and the fact that sin²A+cos²A=1. In fact this will lead pretty swiftly to the equation that you had previously introduced.

Note that you should avoid unnecessary use of the sqrt() function. In particular, prefer the use of the square of magnitudes:
|a|²=a.a (dot product of a with itself).
dot() is an extremely useful function to define in code here.

The way you are solving the problem you might as well go straight to 3-d: there are (slightly) simpler ways of solving the problem in 2-d.

But please note also my comments to @MonkeyD. Having long coordinate expansions just attracts bugs and makes code indecipherable.

MonkeyD wrote:

But Q(t) is in the dot product. So, if we want the quadratic expression in terms of t, we have to get it out of the dot product, don't you think so?

(Q(t) - P).(C - P)
=(Q₀+td - P).(C - P)
=(Q₀ - P).(C - P)+td.(C - P)
=(constant1) + t (constant2)

There, I've extracted t from a dot product for you!!!!

[quirky1234]

@lastchance I have checked my code for 3 examples and it is working fine for them. But when it comes to submitting code, it passes only first test case. Please, show me the way to solve it.
I followed this link: http://paulbourke.net/geometry/circlesphere/
Here's my code:

#include <bits/stdc++.h>
using namespace std;
 
#define speed ios::sync_with_stdio(false)
#define ll long long int
#define ld long double
#define gcd(a,b) __gcd(a,b)
int checkPrimeNumber(int);ll result[1000] = {0};
#define FOR(i,n) for(int i=0;i<n;i++)
#define NO_OF_CHARS 256
#define mod 1e9+7
int main() {
        speed;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
      double px,py,pz,qx,qy,qz,dx,dy,dz,cx,cy,cz,r;
      cin>>px>>py>>pz>>qx>>qy>>qz>>dx>>dy>>dz>>cx>>cy>>cz>>r;
      ll B = (dx*(px-cx))+(dy*(py-cy))+(dz*(pz-cz));
      ll A = ((qx-px)*(px-cx))+((qy-py)*(py-cy))+((qz-pz)*(pz-cz));
      ll C = ((cx-px)*(cx-px))+((cy-py)*(cy-py))+((cz-pz)*(cz-pz))-(r*r);
      ll D = (dx*dx)+(dy*dy)+(dz*dz);
      ll E = ((qx-px)*(qx-px))+((qy-py)*(qy-py))+((qz-pz)*(qz-pz));
      ll F = (2)*(((qx-px)*dx)+((qy-py)*dy)+((qz-pz)*dz));
      ll a = (B*B)-(C*D);
      ll b = ((2*A)*B)-(C*F);
      ll c = (A*A)-(C*E);
      double G = sqrt((b*b)-(4*a*c));
      
      if(a==0)
      {
      	double ans = (double)(-c)/(double)(b);
      	cout<<setprecision(6)<<ans<<endl;
      }
      else 
      {
      	double ans = ((double)(-b)+(double)(G))/(double)(2*a);
           double ans1 = ((double)(-b)-(double)(G))/(double)(2*a);
           //cout<<ans<<endl;
           //cout<<ans1<<endl;
            if(ans>0&&ans1>0)cout<<setprecision(6)<<min(ans,ans1)<<endl;
           else if(ans<0&&ans1>0)cout<<setprecision(6)<<ans1<<endl;
           else if(ans>0&&ans1<0)cout<<setprecision(6)<<ans<<endl;
      }
    }
    return 0;
}

[DGLCfSEw]

@lastchance Event though I really appreciate you putting so much time for us to understand this problem which is fairly simple for you. But, you completely missed my point. I know how to take that out of the dot product, what I asked was, should I take t out of dot product?

I know am a little slow for your speed but please help me understand this.

The equation :
r2 = { mag(C - P) }2 - { dotProduct( Q(t) - P, C - P ) }2 / { mag( Q(t) - P ) }2

I multiplied the denominator to both sides, after that what I don't get is, what to do with the dot product?

Since, we can't let t be in the dot product, I tried to open it by this prop. a · b = ax × bx + ay × by(given here: https://www.mathsisfun.com/algebra/vectors-dot-product.html), but that just simply gives me the wrong ans, I don't understand how to deal with the dot product in the equation...

[closed account j8MNvCM9]

Hey @lastchance!
It is a request!Please show us beginners to get to the real value of "a","b" and "c".
I understand its quiet easy for professionals like you to solve such stuff.

I recommend you to please solve it .

[lastchance]

MonkeyD wrote:

what I asked was, should I take t out of dot product?

And that's EXACTLY what I have told you.

(Q(t) - P).(C - P)
=(Q₀+td - P).(C - P)
=(Q₀ - P).(C - P)+td.(C - P)
=(constant1) + t (constant2)

There, I've extracted t from a dot product for you!!!!

Do this for both terms with a t in. Then proceed as for normal algebra. All you have got left are constants and brackets of the form (m+nt).

the1marvellous wrote:

It is a request!Please show us beginners to get to the real value of "a","b" and "c".
I recommend you to please solve it .

That simply amounts to giving you the solution of the problem. Nothing learned.

[closed account 3UohqMoL]

@lastchance what can be the class design for it as we cannot handle parameter t using class for vector

[closed account j8MNvCM9]

So,please someone post the values of the quadratic co-efficients if someone gets it all correct.

[DGLCfSEw]

@lastchance Which both terms?? Am getting confused a lot uhhh...

there is only one dot product with t in it? right?
there are two terms with t in it in magnitude form? right?

Wait:

|(Q(t)-P)|^2*r^2=|C-P|^2 * |Q(t)-P|^2 - {dotproduct(Q(t)-P,C-P)}

this would be the equation right? after this, Open Q(t) and for magnitude, we will do this :

|Q(t)-P|^2 = (qx+tdx-px)^2+(qy+tdy-py)^2+(qz+tdz-pz)^2 and then we separate t for the quadratic equation..right?

Am sorry btw for asking so much, I just want to clear my doubts and no need to solve it, your guidance is sufficient.