Wesley's Anger Contest 4 Problem 3 - Squirrel Tag

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 4.0s
Python 6.0s
Memory limit: 256M

Problem types

Michael is feeling cooped up in the middle of quarantine and wants to go outside for a bit of exercise; he misses the good old grade school days when he played tag daily with his friends. However, he can't play tag with other people right now, for fear of infection, so he must find other playmates. And who better to chase around than playful little squirrels? There are N squirrels scattered around the (x,y) plane, each represented as a 4-tuple of integers (sx_i,sy_i,vx_i,vy_i), where the i^{th} squirrel starts at the point (sx_i,sy_i) and moves in the direction vector (vx_i,vy_i); that is, every second the squirrel moves vx_i units in the x direction and vy_i units in the y direction. Michael starts at the origin (0,0) and wants to know, if he can move at a speed of S units/second, what is the minimum amount of time (in seconds) it will take for him to catch all of the squirrels?

We consider Michael to have caught a squirrel if they occupy the same (x,y) coordinate at the same point in time. Michael can catch multiple squirrels simultaneously (if they're all at the same location) and needs to catch each squirrel only once.

For this problem, Python users are recommended to use PyPy over CPython.


For this problem, you will NOT be required to pass all the samples to receive points, and you are NOT required to pass all previous subtasks to receive points for a specific subtask.

For all subtasks:

1 \le N \le 15
0 \le |sx_i|,|sy_i| \le 100
0 \le |vx_i|,|vy_i| \le 10
1 \le S \le 100

It is guaranteed that Michael moves strictly faster than all of the squirrels (so a solution always exists).

Subtask 1 [24%]

sy_i,vy_i = 0 for all 1 \le i \le N

Subtask 2 [26%]

1 \le N \le 8

Subtask 3 [50%]

No additional constraints.

Input Specification

On the first line will be two integers N and S, the number of squirrels and Michael's speed, respectively.

The next N lines of input will each contain 4 integers sx_i,sy_i,vx_i,vy_i, the starting position and movement vector of the i^{th} squirrel.

Output Specification

This problem is graded with a custom checker.

Output a single decimal number, the minimum time it will take for Michael to catch all of the squirrels. It is guaranteed that in the given test cases the answer will have value less than 10^{15}.

Your answer will be considered correct if it has an absolute or relative error of at most 10^{-5} from the reference solution. It is guaranteed that the absolute or relative error of the reference solution is much smaller than 10^{-5} from the optimal solution.

Sample Input 1

1 2
1 1 1 1

Sample Output 1


Sample Explanation 1

Michael runs with all his might with velocity (\sqrt 2,\sqrt 2) and arrives at (\sqrt 2+2,\sqrt 2+2) at the exact same time as the squirrel: at \sqrt 2+1 seconds.

Sample Input 2

2 4
8 0 -2 0
-10 0 -2 0

Sample Output 2


Sample Explanation 2

Michael and squirrel two run to (-20,0) in five seconds. Then, squirrel one is at (-2,0), and then Michael changes direction and they both run another three seconds to meet at (-8,0).

Sample Input 3

5 15
10 15 1 10
-10 -2 -6 -10
5 -19 -10 -5
-5 5 -1 -3
5 2 3 0

Sample Output 3


Sample Explanation 3

Michael catches the squirrels in the order 2,3,4,5,1.


There are no comments at the moment.