Problem LinkAuthor: Rahim Mammadli Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyEASYMEDIUM PrerequisitesCross Product, Binary Search ProblemGiven a stationary point $P$ and a point $Q$ moving in straight line, indicate the time when $Q$ is visible from $P$, given that there am opaque sphere between them. ExplanationWe will try to find the solution in 2D and then extend the idea to 3D as well. From the above figure, the first idea which can be clearly concluded is that, once point $Q$ becomes visible from $P$, it will remain visible forever. Before that, it will always remain invisible. This, the function (whether $Q$ is visible $P$ at given time $t$) follows the idea that it is false initially and after a certain point, it always remains true. This hints that we can binary search on the answer and just need to check whether the point $Q$ is visible from $P$ at given time $t$ or not. For more ideas on "Binary search" on such type of problem, refer to this awesome tutorial on topcoder. Hence, solution template looks like:
So, given a particular time $t$, we can first calculate the position of point $Q$. Join $P$ and $Q$ by a straight line. If the line doesn't pass through the circle, the point $Q$ is visible from $P$ else it is not visible. To check if a given line passes through the circle or not, it is enough to check that the perpendicular distance of the line from the centre, $C$, of the circle is greater than the radius, $r$, of the circle. For this, we first complete the triangle $PCQ$ and let the perpendicular distance of $PQ$ from $C$ be denoted by $CO$. Using the formula, $$\text{Area of triangle} = \frac{1}{2} * \text{Base} * \text{Height} = \frac{1}{2} * CO * PQ$$ Since the area of the triangle can be found given 3 points in 2D, and $PQ$ is the Euclidean distance between $P$ and $Q$, we can find the value of $CO$ efficiently. Finally, we just need to compare it to $r$, the radius of the circle. For extending the solution in 3D, the idea is same and we just need to find the area of a triangle in 3D. For details, one can refer here. It can be clearly seen that the above formula holds for the 2D case as well. $$\text{Area of triangle in 2/3D} = \frac{CP X CQ}{2}$$ where $CP$ and $CQ$ are vectors, $a X b$ denotes cross product of vectors and $a$ denotes the magnitude of vector. Thus, to find the length of $CO$, we have $$CO = \frac{2 * \text{Area of triangle PCQ}}{PQ} = \frac{CP X CQ}{PQ}$$ For more details, you may refer to the editorialist solution which exactly follows the above idea. Extra Ideas/CaveatsThe binary search implementation mentioned in the editorial is different from the one mentioned in Topcoder tutorial. Though both will give AC here, the one in Topcoder needs one to correctly set the Epsilon value for termination condition and sometimes can lead to wrong answers due to precision issues. The editorialist just prefers the above style to implement binary and ternary search involving doubles as calculation of epsilon is not required. Also, for details regarding the exact number of iterations or complexity analysis for binary search problem on doubles, refer to this blog on codeforces. Note from the authorFinding the distance of a point from a line in 3D is a generally common problem and also contains some edge cases where the point may not lie within the line segment region. But given the constraints of the problems, there are no edge cases but we should be aware of it in general. Feel free to share your approach, if it was somewhat different. Time Complexity$O(LogN)$ per test case (around 100 iterations for binary search). Space Complexity$O(1)$ AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here.
This question is marked "community wiki".
asked 06 Jun, 01:17

Alternative approach to checking whether Q(t) is visible from P or not at a given time t: Obtain a parametric equation of the line joining P and Q(t) in terms of some parameter (say a) which varies from 0 to 1. Any point (x, y, z) lying on this line can be written in terms of a as: x = Px.(1a) + Qx(t).a y = Py.(1a) + Qy(t).a z = Pz.(1a) + Qz(t).a At a = 0, you are at point P and at a = 1, you are at point Q(t). At any a between 0 and 1, you are at some point in the line between P and Q(t). Now we substitute (x, y, z) in terms of the parameter a in the equation of the sphere. We will obtain an equation in terms of t and a, which will be a quadratic in the parameter a. The point of tangency is when this quadratic has exactly one root, so we binary search on t, searching for that t when the quadratic's discriminant becomes zero. Link to my solution: https://www.codechef.com/viewsolution/18755742 answered 11 Jun, 16:04

I used simple 3D Coordinate Geometry. Now, the equation of line PQ' in parametric form(with parameter k) is, X = P_{x} + (Q'_{x}P_{x})k Now, equation of sphere is, answered 11 Jun, 16:05
Hi @adzo261, I have followed a similar approach but getting WA. Can you show me your correct submission?
(14 Jun, 14:56)

If D is the point upto which Q goes, then (PCXPD)/PD=r If k is the time, a quadratic in k can easily be solved. My solution:https://www.codechef.com/viewsolution/18852174 answered 11 Jun, 16:15

Or Take the Reference of this site to solve this. http://www.ambrsoft.com/TrigoCalc/Sphere/SpherLineIntersection_.htm Condition on :B * B4 * A * C SInce it is Monotonic.We can use Binary Search answered 11 Jun, 18:43

I think test cases were weak during contest as per given case by @soham1234 1 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. answered 11 Jun, 23:06

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). Easy solution : https://www.codechef.com/viewsolution/18820388 answered 12 Jun, 12:56

I used the same approach as mentioned in the editorial using python 3. I am getting TLE for 6 out of 7 tasks. The link for the code is: Could anyone please check and see whats wrong with my code. It will be of great help. Thanks!! answered 16 Jun, 17:37
1
@zymbio, I saw your solution and it is totally correct. It will TLE just because python is slow. Try submitting in "pypy" or using the number of iterations as 75 (finding the exact number of iterations has been added as link in the editorial)
(17 Jun, 14:32)
sure! will also go through the link :) thanks !!
(17 Jun, 19:46)

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
Time Complexity O(1) per test case reminds me of https://codeforces.com/blog/entry/58667 xD
What? I think I edited that section out for correction xD. Where is it left now? :p
PS: Great blog you found :p