A meteor shower is approaching the Monkey Empire. At the titith second, a meteor will fall at (xi,yi)(xi,yi) and destroy the planet. Luckily, the monkeys have a square tarp that they can use to catch the meteors. They can set up the tarp at any location initially at time 00, but once it has been set, the tarp can only be moved by up to KK units in
See Also : Canada Day Contest 2021
the ±x±x and ±y±y direction per second independently (You can move KK units in both directions at once). In addition, the tarp is aligned with the xx and yy axis and cannot be rotated. What is the minimum tarp side length required to catch all meteors?
Assume the meteors have insignificant size.
The first line contains an integer nn, the number of meteors, and KK, the tarp speed.
The next nn lines contain three integers each: titi, xixi, and yiyi, the time and location of the iith meteor strike. The input is given in order of nondecreasing time.
Output the minimum side length of the tarp.
Sample Input 1
2 0 1 0 0 2 0 3
Sample Output 1
Explanation For Sample 1
The tarp has a speed of 00, so it cannot move. It must be big enough to cover both (0,0)(0,0) and (0,3)(0,3) at the same time.
Sample Input 2
2 1 1 0 0 2 3 3
Sample Output 2
Explanation For Sample 2
At time 11, the bottom left corner of the tarp is at (0,0)(0,0). It moves 1 unit up and right by time 22. The top right corner now covers (3,3)(3,3).
Sample Input 3
3 1 1 100 100 3 100 105 103 0 5
Sample Output 3
Explanation For Sample 3
The tarp starts with the bottom left corner at (100,100)(100,100) to catch the second meteor, moves 22 units up to catch the third meteor, then moves 100100 units left to catch the first meteor.
Sample Input 4
3 1000 1 0 0 1 5 1 2 100 100
Sample Output 4
Sample Input 5
3 100 0 1 3 1 4 2 5 0 0
Sample Output 5
This is actually a 1 dimensional problem. We can consider each dimension separately, then take the maximum of the width and length as the solution.
You can use binary search for this problem but it’s not necessary. Let rr be the minimum current position of a the tarp’s right edge and ll be the maximum position of the tarp’s left edge, out of every path it could have taken to cover all the meteors so far. Initially, l=∞,r=−∞l=∞,r=−∞. Every second, ll increases by KK and rr decreases by KK, as the tarp could have travelled up to KK units to the left or right. When a meteor at xx is encountered, l=min(l,x),r=max(r,x)l=min(l,x),r=max(r,x) to ensure the tarp covers the meteor. Find the answer by taking the maximum of r−lr−l after every meteor encounter.