Maximum Minimum Manhattan Distance

Given N offices on a 2D grid, each identified by coordinates, your task is to compute the maximum among the minimum Manhattan distances between every office and any other office. For each office \(i\), define its minimum Manhattan distance as

\(\min_{\substack{1 \leq j \leq N \\ j \neq i}} \left(|x_i - x_j| + |y_i - y_j|\right)\)

You are required to find and output the value of

\(\max_{1 \leq i \leq N} \left( \min_{\substack{1 \leq j \leq N \\ j \neq i}} \left(|x_i - x_j| + |y_i - y_j|\right) \right)\)

Input is read from standard input and the result should be printed to standard output.

inputFormat

The input starts with a single integer N indicating the number of offices. The next N lines each contain two space-separated integers representing the coordinates \(x\) and \(y\) of an office.

outputFormat

Output a single integer which is the maximum of the minimum Manhattan distances between any two distinct offices.

4
0 0
2 2
3 3
5 5

4