You are not logged in. Please login at www.codechef.com to post your questions!

×

Please help me in ZUBGOLD from Kolkata Onsite.

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?

asked 31 Jan '18, 01:41

sk018's gravatar image

4★sk018
111
accept rate: 0%

edited 08 Mar '18, 02:28

meooow's gravatar image

6★meooow ♦
7.0k718


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.
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 :)

link

answered 02 Feb '18, 02:56

meooow's gravatar image

6★meooow ♦
7.0k718
accept rate: 48%

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

(02 Feb '18, 15:19) admin ♦♦0★

Oh cool, I hadn't noticed that. The answer indeed doesn't depend on $S$ :D
So I guess the purpose of $S$ here is only to determine the plane of the forest.

(08 Mar '18, 02:26) meooow ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,698
×1,101
×1,056
×3
×1

question asked: 31 Jan '18, 01:41

question was seen: 360 times

last updated: 08 Mar '18, 02:28