Mole Catching
Time limit2sMemory limit128 MB
Given N moles with positions and appearance times, find the maximum number Jeongeun can catch by moving at speed at most S from origin at time 0.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Sorting, Geometry
- Solved
- No attempts yet
Problem
Jeongeun is playing a mole-catching game in a wide field. Exactly T seconds after the game starts, one mole appears at coordinate (x, y). A mole appears only for an instant, so Jeongeun catches it only if she is at that coordinate at exactly that time. Arriving at the coordinate exactly at that time also counts.
There are N moles. Jeongeun starts at (0, 0) and can move at most S units of distance per second. For example, moving from (0, 0) to (1, 1) requires distance sqrt(2).
Given the position and time of each mole, compute the maximum number of moles Jeongeun can catch.
Constraints:
1 <= N <= 6,6661 <= S <= 1,0001 <= T <= 1,000,000,0000 <= |x|, |y| <= 1,000
Input
The first line contains two integers N and S.
Each of the next N lines contains three integers x, y, and T describing one mole. T is the number of seconds after the game starts when that mole appears. At time 0, Jeongeun is at (0, 0).
Output
Print the maximum number of moles Jeongeun can catch.