One dimensionality of Manhattan-distance
Let us understand the Manhattan-distance.
Here is one remarkable phenomenon. Every one of the points (0,1), (1,0), (2, -1) is 6 distance away from every one of the points (3, 4), (4, 3), (5, 2).
We can imagine that the former three points correspond to $1=0+1=1+0=2+(-1)$ on the number line and that the later three points correspond to $7=3+4=4+3=5+2$ on the number line as the distance between 1 and 7 is 6. We can say Manhattan-distance on the coordinate plane is one dimensional almost everywhere.
One dimensionality of Manhattan-distance. The Manhattan-distance of two points $(x_1, y_1)$ and $(x_2, y_2)$ is either $|(x_1+y_1)-(x_2+y_2)|$ or $|(x_1-y_1)-(x_2-y_2)|$, whichever is larger.
$$ d((x_1, y_1),(x_2, y_2))= \max(|(x_1+y_1)-(x_2+y_2)|, |(x_1-y_1)-(x_2-y_2)|)$$
With this understanding, it is not difficult to construct the algorithm that computes minMax, the wanted minimum of the maximum Manhattan distance of a point to the given points and count, the number of all points that reach that minMax.
Algorithm
- Loop through all given points $(x,y)$ to compute the following.
- minSum, the minimum of all $x+y$.
- maxSum, the maximum of all $x+y$.
- minDiff, the minimum of all $x-y$.
- maxDiff, the maximum of all $x-y$.
According to the one dimensionality, we know minmax is the minimum of max((p+q)-minSum, maxSum-(p+q), (p-q)-minDiff, maxDiff-(p-q)) where (p,q) goes through all lattice points.
- Let rangeSum = maxSum - minSum and rangeDiff = maxDiff - minDiff.
- Let $s$ = min(rangeSum, rangeDiff) and $b$ = max(rangeSum, rangeDiff).
- Let minMax = $b/2+1$ if both $s$ and $b$ are even and $(s-b)/2$ is odd. Otherwise, let minMax = $\lceil (b+1)/2\rceil$.
Once we have obtained the minMax, we can find all points whose maximum Manhattan-distance to points on the grid is minMax.
- Let count = 0.
- Run a nested loop, where
i
runs from (maxSum - minMax) to (minSum + minMax) and j
runs from (maxDiff - minMax) to (minDiff + minMax), all inclusively. Whenever i+j
is an even number, increase count by 1 since we get a point ((i+j)/2, (i-j)/2)
whose maximum Manhattan-distance to the given points is minMax.
Time complexity
The only place that may run longer than $O(N)$ is the step 6. We can see that either (minSum + minMax) - (maxSum - minMax) <= 1 or (minDiff + minMax) - (maxDiff - minMax) <= 1
So the nested loops is basically one loop run at most twice. So step 6 takes at most $O(M)$ time, where $M$ is the maximum absolute value of the coordinates of the given points.
The algorithm above runs in $O(N + M)$ time, which should be faster enough to solve the original contest problem.
Here are two easy exercises.
Exercise 1. Prove one dimensionality of Manhattan-distance stated above. Show the algorithm above is correct.
Exercise 2. Speed up step 6 of the algorithm so that the step 6 will run in $O(1)$ time. The improved algorithm will run in $O(N)$ time.