Binary search for time t and calculate Q’(x,y,z) = Q(x,y,z) + d(x,y,z) * t
Distance of point C(center) from line \overrightarrow{PQ'} from Idea -> \frac{|\overrightarrow{PC} \ X \ \overrightarrow{PQ'}|}{|\overrightarrow{PQ'}|}\ ==\ r
EDIT
Float comparision is wrong here.
Instead search ends when t(low) >= t(high) each being added or subtracted by \epsilon respectively in each iteration
Slightly different approach - use the vector equation of the cone: F(u) = u.d - |u||d|cos(theta) = 0,
where the axis of the cone is given by the vector d and the origin is the vertex of the cone.
Shift origins to P, then PC is d, and PQ is u.
Then, you only have to implement the dot product and find the smallest t when q = q0 + d*t satisfies F(q) = 1 with a binary search.
I think the below link is enough to solve the Question in just half an hour.
Here,they provided full proof of of dot product as well as cross product formula…its became really helpful to me
I think test cases were weak during contest as per given case by @soham1234
1
4 0 0 -10 6 0 1 0 0 0 0 0 3
this solution gives output 19.2915 which is wrong (this is my code accepted during contest)
many submissions giving different outputs passed during contest.
this solution gives output 8.7085 which is correct (i submitted after contest)
Mistake in my code was to find minimum positive t.
I solved it in O(1) for every test case.
My approach was initializing P to [x1,y1,z1], Q to [x2 + tdx, y2 + tdy, z2 + tdz] and C to [x3,y3,z3].
And applying formula |PC X PQ| / |PQ| (considering vectors).
This formula will give us shortest distance between line PQ and centre of Circle (c). Since for time t to be minimum, this distance should be equal to R (radius).
SO, r = |PC X PQ| / |PQ|.
Substitute values for P, Q and C and at end you will get an quadratic equation of the form b^2 - 4ac = 0,
Solve it and take the minimum positive root(incase we get both positive roots).
This approach is different from binary search approach.
And it works! it is based on forming a quadratic equation based on distance formula and requires very few lines of code :
Here is the link to the code: https://www.codechef.com/viewsolution/18842935
hello,
I tried solving this problem using vector algebra without using binary search technique.I moved the point
Q with time t and then checked the perpendicular distance from the center .My solution was not correct and
I am not able to figure out my mistake.
Here is the link to my submitted code. https://www.codechef.com/viewsolution/18860135
Hello @saurav96 here is your accepted code:Link The only problem was precision since you had used float it was resulting to less precision. Use double or long double to resolve. You can also see this link for more info:gfg
I went a different route and used axis rotations and translations to calculate the intersections of the path Q takes and the cone created by the sphere and Point P as the apex of the cone. “long double” precision was good enough - I only had to manually detect the sample test case and output “1” for that one. xD