VSN - Editorial

likecs · June 6, 2018, 1:17am

Problem Link

Practice

Contest

Author: Rahim Mammadli

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

Cross Product, Binary Search

Problem

Given 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.

Explanation

We will try to find the solution in 2-D and then extend the idea to 3-D 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:


	double low = 0, high = 10^18
	for i in [1, 100]:
		double mid = (low + high) / 2
		if visible(P, Q, C, r, mid):
			high = mid
		else:
			low = mid
	double ans = (low + high) / 2

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 2-D, 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 3-D, the idea is same and we just need to find the area of a triangle in 3-D. For details, one can refer here. It can be clearly seen that the above formula holds for the 2-D case as well.

\text{Area of triangle in 2/3-D} = \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/Caveats

The 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 author

Finding the distance of a point from a line in 3-D 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.

vijju123 · June 11, 2018, 3:54pm

I think the time complexity of O(1) per test case is a typo. Although the solutions arent available right now, I can make a guess that the implementation referred to is something like “Binary search at least 100-200 times.” to get the answer, that value of 100-200 is based on the value of N. We know the value of LogN and set a value higher than that as limit.

Can you please share the code snippet you’re talking about (I am assuming its not the topcoder one but the one in editorialist solution), if my above argument isnt applicable to your solution?

likecs · June 11, 2018, 3:58pm

O notation doesn’t take into account constant factors. Still updated it for reference.

likecs · June 11, 2018, 3:59pm

code snippet is same as the one mentioned in editorial

schleppel · June 11, 2018, 4:00pm

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

kishore_p · June 11, 2018, 4:02pm

Just adding one more point ,we are basically finding the time at which line joining PQ’ is tangent to sphere,
where Q’=Q0+dt and solving for t.Final eqn is same as mentioned in the editorial

vijju123 · June 11, 2018, 4:03pm

What I wanted to say was, that constant was based on your N. You wont be using the same 100 iteration for high={10}^{1000}. The doubt I had is, that, this K (where K is no. of iterations) must be \ge logN. Hence I feel its theoretically wrong to call it O(1). Am I right? Or am I missing something?

pshishod2645 · June 11, 2018, 4:04pm

Want to mention two things:

Complexity is not O(1) per test case (As this will confuse ones who are new to discrete binary search) :The number of iterations (100 in this case) will need to be adjusted if tmax is larger, actual time complexity if O(log_2{t_{max})}, (per test case) in this case.
To get precision upto n decimal places, setting epilson as 10^{-n-1} will work fine as both low and high will be same upto n decimal places.

akamoha · June 11, 2018, 4:04pm

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.(1-a) + Qx(t).a

y = Py.(1-a) + Qy(t).a

z = Pz.(1-a) + 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

adzo261 · June 11, 2018, 4:05pm

I used simple 3D Coordinate Geometry.

Let the general point on which point Q is traveling be Q’.

Therefore,

Q’_x=Q_x + D_xt

Q’_y=Q_y + D_yt

Q’_z=Q_z + D_zt

Now, the equation of line PQ’ in parametric form(with parameter k) is,

X = P_x + (Q’_x-P_x)k

Y = P_y + (Q’_y-P_y)k

Z = P_z + (Q’_z-P_z)k

Now, equation of sphere is,

(X-C_x)² + (Y-C_y)² +(Z-C_z)² = R²

Now solve Line PQ’ with equation of sphere, and we will get a quadratic equation in parameter k.

For condition of tangency(single solution), delta must be equal to zero.

So calculate delta and make it equal to zero, and here we get another quadratic in t.

Solve for t and consider the postitive value ,since it is time.

vijju123 · June 11, 2018, 4:06pm

Yes, that was exactly my point!

likecs · June 11, 2018, 4:09pm

Seems Ok. Will update it in a while.

vijju123 · June 11, 2018, 4:10pm

Thanks

cloudsandrain · June 11, 2018, 4:15pm

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

hidden_shadow · June 11, 2018, 5:12pm

Can somebody tell why my solution was not working ? Still not getting it. https://www.codechef.com/viewsolution/18838079 exact same method and took care of out of bound situations as well.

l_returns · June 11, 2018, 5:30pm

was expecting this… PS: I have tried many solutions for this one… one of them luckily worked…

kukreja_vlk · June 11, 2018, 6:33pm

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

potatio · June 11, 2018, 6:40pm

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.

Solution here.

doramon · June 11, 2018, 6:43pm

Or Take the Reference of this site to solve this.

http://www.ambrsoft.com/TrigoCalc/Sphere/SpherLineIntersection_.htm

Condition on :B * B-4 * A * C

SInce it is Monotonic.We can use Binary Search

vijju123 · June 11, 2018, 6:55pm

|PC x PQ'| / |PQ'| == r

You are comparing float here!