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 squirrels scattered around the plane, each represented as a -tuple of integers , where the squirrel starts at the point and moves in the direction vector ; that is, every second the squirrel moves units in the direction and units in the direction. Michael starts at the origin and wants to know, if he can move at a speed of 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 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:
It is guaranteed that Michael moves strictly faster than all of the squirrels (so a solution always exists).
Subtask 1 [24%]
Subtask 2 [26%]
Subtask 3 [50%]
No additional constraints.
On the first line will be two integers and , the number of squirrels and Michael's speed, respectively.
The next lines of input will each contain integers , the starting position and movement vector of the squirrel.
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 .
Your answer will be considered correct if it has an absolute or relative error of at most from the reference solution. It is guaranteed that the absolute or relative error of the reference solution is much smaller than 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 and arrives at at the exact same time as the squirrel: at 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 in five seconds. Then, squirrel one is at , and then Michael changes direction and they both run another three seconds to meet at .
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 .