VSN - Editorial

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

Want to mention two things:

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

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

5 Likes

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: CodeChef: Practical coding for everyone

5 Likes

I used simple 3D Coordinate Geometry.

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

Therefore,

Q’x=Qx + Dxt

Q’y=Qy + Dyt

Q’z=Qz + Dzt

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

X = Px + (Q’x-Px)k

Y = Py + (Q’y-Py)k

Z = Pz + (Q’z-Pz)k

Now, equation of sphere is,

(X-Cx)2 + (Y-Cy)2 +(Z-Cz)2 = R2

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.

4 Likes

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:CodeChef: Practical coding for everyone

3 Likes

Can somebody tell why my solution was not working ? Still not getting it. CodeChef: Practical coding for everyone exact same method and took care of out of bound situations as well.

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.

Solution here.

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

1 Like

Can you prove that binary search will give the correct answer in max 100 iterations?

My submission: TLE submission

Source of condition: Line Sphere intersection

Hi. Both Author’s and Editorialist’s solution fail in this test case:

1
4 0 0 -10 6 0 1 0 0 0 0 0 3

I mailed the testcase to Misha 2 days before the contest ended but it wasn’t updated. Any reason why?

Edit:He mailed . He was busy for his exams so didn’t see my mail before.

3 Likes

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 :slight_smile:

link: Point-Line Distance--3-Dimensional -- from Wolfram MathWorld

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.

1 Like

I did not use binary search.

Point P will make an enveloping cone (cone by tangents) C to sphere. Find equation of C.

Point Q with vector d, will make a straight line (ray) L. Find equation of L.

Now the point of intersection of C and L is the required point, which will give minimum time t after solving.

Per test case O(1) solution:
https://www.codechef.com/viewsolution/18861170

my solution
Could anyone please tell me what is the mistake in my code?
I’m getting the most precise answer;

Anyone having solution without binary search ??? my solution

Anyone with a similar approach and working well please post your solution in the comment section :slight_smile:

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 : CodeChef: Practical coding for everyone

1 Like

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

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:

  • https://ideone.com/IZ6ikK
  • Could anyone please check and see whats wrong with my code.
    It will be of great help. Thanks!!

    1 Like