Editorial for ECOO '13 R2 P2 - The Walking Dead


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

You have the centre of each zombie's circle and their current position. You can get the radius of the circle by computing the distance between these two points with the Pythagorean theorem. Then you can get the distance a zombie walks by multiplying the countdown time by its speed. The tricky part is then figuring out where the zombie will end up.

First, compute the circumference of the circle (C = 2 \pi r). Then divide the distance walked by the circumference. This gets you a number that represents how far around the circle they went (e.g. if you end up with 0.5 then they walked half way around the circle, which is 180 degrees or \pi radians).

Now translate the circle to the origin by subtracting C_x and C_y from the zombie's position. You can figure out the tangent of the current angle the zombie is making with the x-axis, then use \arctan to get the angle. Now add the angle they walked and use \sin and \cos on this new angle to get x and y coordinates representing where they end up. Because you have translated to the origin, you have to translate back by adding C_x and C_y to the zombie's final position.

Once you have the final position of the zombie, round it to two decimal places and compute the distance to the bomb. If this distance is less than or equal to the blast radius, the zombie is destroyed.

When using arctan to get the angle, your system will probably always return an angle that is between 90 and -90 degrees, which would always put the zombie in quadrant I or IV of the Cartesian plane. Therefore, if your zombie is in quadrants II or III to the left of the y-axis (i.e. to the left of the circle centre before translation) then you will have to add or subtract 180 degrees (\pi radians) to get the real angle. Also, depending on the language you are coding in, you may have trouble with 90 degree or -90 degree angles and you might have to treat them like a special case.


Comments

There are no comments at the moment.