Help with ZUBGOLD Our team was unable to solve this problem in onsite regionals.Can anyone help me in approach? asked 31 Jan '18, 01:41

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 :P 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. 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. The final step is to compute $G = (C + D) / 2$ and output the answer. answered 02 Feb '18, 02:56
1
wow, I didn't know that numpy exists in python (supported at CodeChef :P ). This is great, my solution used typical C++ with own implemented C++ 3D 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.
(02 Feb '18, 15:19)
Oh cool, I hadn't noticed that. The answer indeed doesn't depend on $S$ :D
(08 Mar '18, 02:26)
