No.1998 Manhattan Restaurant
Problem Statement
There are $N$ houses numbered $1, 2, \dots, N$ on a two-dimensional plane. The coordinates of house $i$ $(1 \leq i \leq N)$
are $( X_{i}, Y_{i} )$.
Here, $X_{i}, Y_{i}$ are both even.
Core-san will freely choose any $2$ locations on this plane and build a restaurant at each of them.
Let $d_{i}$ be the smaller of the Manhattan distances from house $i$ $(1 \leq i \leq N)$ to the $2$ restaurants.
Find the minimum possible value of $\max ( d_{1}, d_{2}, \dots, d_{N} )$.
Under the constraints of this problem, it is guaranteed that the answer is always an integer.
Definition of "Manhattan distance" (click to expand)
For any $2$ points $P_{1} ( x_{1}, y_{1} )$, $P_{2} ( x_{2}, y_{2} )$ on a two-dimensional plane,
the Manhattan distance $L^{1} (P_{1}, P_{2} )$ between these $2$ points is defined as follows.
$L^{1} (P_{1}, P_{2} ) := | x_{1} - x_{2} | + | y_{1} - y_{2} | $
Constraints
$1 \leq N \leq 10^{5}$
$N$ is an integer.
$-10^{9} \leq X_{i}, Y_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
$X_{i}$, $Y_{i}$ $(1 \leq i \leq N)$ are even.
Subtasks
Due to yukicoder's specifications, no partial scores are set for this problem, but
the test cases (inputs) of this problem are divided into the following $2$ subtasks.
$N \leq 600$ (up to the $15$-th test case from the top)
No additional constraints.
A submitted solution is judged as AC only if it is correct on both Subtask 1 and Subtask 2.
Please note that if it is incorrect on at least one of Subtask 1 and Subtask 2, it will not be judged as AC.
Input
The input is given in the following format.
$N$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
$\vdots$
$X_{N}$ $Y_{N}$
Line $1$ contains $N$.
Line $(1 + i)$ $(1 \leq i \leq N)$ contains $X_{i}$ and $Y_{i}$ in this order, separated by a single-byte space.
Output
Print the answer on $1$ line, followed by a newline.
Sample
Sample 1
Input
3 2 6 -16 20 0 -2
Output
5
For example, you can build the $2$ restaurants at coordinates $(1,2)$ and $(-16,20)$.
In this case,
$d_{1} = \min ( | 2 - 1 | + | 6 - 2 |, | 2 - (-16) | + | 6 - 20 | ) = 5$,
$d_{2} = \min ( | -16 - 1 | + | 20 - 2 |, | -16 - (-16) | + | -20 - (-20) | ) = 0$,
$d_{3} = \min ( | 0 - 1 | + | -2 - 2 |, | 0 - (-16) | + | -2 - 20 | ) = 5$
and thus $\max( d_{1}, d_{2}, d_{3} ) = 5$.
The value of $\max( d_{1}, d_{2}, d_{3} )$ cannot be made smaller than this, so the answer is $5$.
A restaurant may be built at coordinates where a house already exists.
Sample 2
Input
10 0 12 0 2 4 4 0 12 0 2 0 2 2 0 4 8 0 4 0 8
Output
4
Multiple houses may exist at the same coordinates.
Sample 3
Input
1 100 100
Output
0
Sample 4
Input
10 826 -42644 328 6 620390134 -10369824 -28 305164020 -222219018 -3308 406 467945990 1051026 165620000 178174 -38 -28875428 -515082 -73139174 -121760098
Output
345084361
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
MasKoaTS