PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
This problem is supposed to be the easiest one in this set. Each of the earth and N asteroids start at some initial coordinates and moves in one of the 4 axis parallel directions. We are asked to find the earliest time at which the earth collides with one of the asteroids. Note that the constraints on coordinates are very small, -100 ≤ x,y ≤ 100, so we can just simulate their positions in each second. The 3rd sample case shows that the answer need not be an integer, but if you observe carefully, each object moves only along the grid lines with velocity of 1 unit per second. If you consider the one unit distance between two integer coordinates, they can meet at the end or exactly in the middle. So the answer will always be of the form t.0 or t.5, if there is a collision. One way to take care of this is to multiply the coordinates by 2. Note that all the points now start inside a 400x400 grid and its easy to see that there cannot be collisions outside this grid, and if there is any collision, it will occur no later than t = 400. You can just simulate the positions in each unit of time and do not forget to half the answer finally ( because we multiplied the coordinates by 2 ). Refer writer’s solution for an implementation of this idea.
What if the coordinates were huge, say 109. Given the initial coordinates of two points and their direction of movement, we can find the time at which they collide. Refer tester’s solution.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.