Help with ZUBGOLD
Problem:https://www.codechef.com/KOL17ROL/problems/ZUBGOLD
Our team was unable to solve this problem in onsite regionals.Can anyone help me in approach?
1 Like
To solve this you should be familiar with vectors in 3D space and common operations on them. I imagine it may be solvable with line and plane equations, but that would be very cumbersome. Also, having powers of imagination helps 
So first we represent the plane which is the forest floor. We know the 3 points S, A, and B are on the floor, which means we also know 3 vectors that lie on the floor: \vec{SA}, \vec{SB} and \vec{AB}. The cross product of any 2 vectors is perpendicular to both of them, so we can do that to get a vector perpendicular to the forest floor, \vec{u}.
Now \vec{u} is perpendicular to the floor, but it may be pointing up or down. We need to be know which it is, because the answer will be different if we switch up and down directions. The problem statement gives us the necessary information to determine this by telling us the origin will always be in the sky.
To know which way is up, there are a few methods. Our team checked whether S - \vec{u} is closer to the origin than S + \vec{u}. If so, then \vec{u} is pointing down.
And as far as I remember, the problem setter compared the angle between \vec{u} and \vec{SO} to the angle between -\vec{u} and \vec{SO}.
Note that in both these methods it is not necessary to use S, it works with any point on the plane.
So once we know which way is up, let’s make sure \vec{u} is pointing up by switching \vec{u} to -\vec{u} if necessary and continue.
Now to get to point C we should go to A from S, turn right 90°, and continue the distance SA. In vector terms, C = A + (SA) \cdot \hat{p}, where \hat{p} is a unit vector in the direction which we get by facing the direction \vec{SA} and turning 90° right.
We know \vec{u} is up, so we can again use cross product here. By the right-hand rule, we can get \vec{p} = \vec{SA} \times \vec{u} which will be in the required direction. Then we can normalize it to get the unit vector \hat{p}.
Similarly we can say D = B + (SB) \cdot \hat{q}, where \hat{q} is the unit vector in the direction \vec{u} \times \vec{SB}.
And now we know C and D.
Alternately, as a simpler procedure, we can first normalize \vec{u} to get \hat{u}. Then C = A + \vec{SA} \times \hat{u} and D = B + \hat{u} \times \vec{SB}. It should make sense why this is so.
The final step is to compute G = (C + D) / 2 and output the answer.
Here is an implementation in Python to show that it works: solution. This takes more than 2x the time limit so it’s not advisable to try this in the ICPC, better to stick to C++ or Java.
Hope this helps, and let me know if you have any questions 
1 Like
wow, I didn’t know that numpy exists in python (supported at CodeChef 
). This is great, my solution used typical C++ with own implemented C++ 3-D geometry operations.
One of the most interesting facts was that location of S doesn’t matter in finding the location of gold. So, you can potentially choose some other “nice” point to be “S”. That way, your answer will be join line AB, Rotate AB by 45’, let the new point be C. Answer will be point D which is mid point of A and C.
1 Like
Oh cool, I hadn’t noticed that. The answer indeed doesn’t depend on S 
So I guess the purpose of S here is only to determine the plane of the forest.