I think it is clear till the binary search part (if not then do let me know).

For now, I'll explain how to check if it is possible to assign a new delivery office such that the max distance to a cell from the closest delivery cell is reduced to upto k.

Notice that |a|+|b| = max(|a+b|,|a-b|), where |x| = abs(x) = absolute value of x

Therefore, manhattan_distance = |x1-x2|+|y1-y2| = max(|x1-x2 + y1-y2|,|x1-x2-(y1-y2)|)

= max(|(x1+y1)-(x2+y2)|, |(x1-y1)-(x2-y2)|)

Now, if you fix a cell as a delivery office, say (x2,y2) is fixed, you just need to find the maximum distance to a cell. Now think how can you maximize the above expression when (x2,y2) is fixed. Only when you either maximize or minimize (x1+y1) or (x1-y1) (In total 4 cases). So, precalculate the 4 cells (which do not have a delivery office and the initial distance to a delivery cell is greater than k) which satisfy either of the 4 above cases. Now for each cell as a new delivery office, calculate the distance from this cell to the 4 cells (precalculated) and take the maximum distance.

Check if this maximum distance is less than k or not.