Vicky For Vendetta
All submissions for this problem are available.
Revenge is once again high on the mind of obnoxious Vicky. Vicky is chasing N of his friends including Abhishek, Atishay, Ankit and Abhijeet who he thinks have stolen his candy. The ith friend is at ( xi, yi ) at t = 0 and is moving with a constant velocity of ( vxi, vyi ), such that the ith friend is at ( xi + vxi, yi + vyi) at t = 1 and at ( xi + 2*vxi, yi + 2*vyi ) and so on. Vicky himself is at (x, y) and has M possible choices of velocity to move with. However once he has chosen a velocity he can move only with that constant velocity throughout the journey. The way these velocities are expressed and the way Vicky moves after he has chosen a particular velocity follow the same constraints as that of his friends.
Vicky has got one flash bomb and wants to burst it at a location (which is his own location at that moment) where he can drive as many of his friends blind as possible. The range till which the bomb has its effect is different for different friends. More formally, the range for the ith friend is ri, and the ith friend will be affected by the bomb only if he is within the range ri of the bomb.
Vicky intends to choose and move with the velocity that will take him to a location where he can harm as many of his friends as possible. Help obnoxious Vicky find out the number of friends he can hurt by making the best choice.
The first line of the input file consists of two space separated integers M and N, followed by another line containing two space separated integer x, y. This is followed by M lines containing M possible velocities to choose from. More formally, the jth line contains two space separated integers vxj and vyj Vicky can choose to move with. Thereafter N lines follow describing N different friends. The ith line of these N lines contains 5 space separated integers xi, yi, vxi, vyi, ri.
Print a single integer which is the maximum number of friends Vicky can hurt making the optimal choice.
1 <= M <= 1000 1 <= N <= 1000 -1000 <= x, y, vx, vy, xi, yi, vxi, vyi <= 1000 1 <= ri <= 2500
Input: 1 3 0 0 0 2 0 -3 0 4 1 1 2 -1 1 1 1 -2 2 -1 1 Output: 2 Explanation: At time 1.5, Vicky is at point (0, 3), and the three friends are at points (0, 3), (-0.5, 3.5), and (4, -3.5).
The first two friends are within 1 unit of Vicky, while the third will never be within 1 unit of Vicky.
|Time Limit:||0.17 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, GO, NODEJS, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.