問題一覧 > 通常問題

No.1998 Manhattan Restaurant

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 33
作問者 : MasKoaTS / テスター : 👑 potato167 👑 cologne
お気に入りにしたユーザー ProblemId : 7915 / 自分の提出
問題文最終更新日: 2024-11-28 20:21:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 350 (順位表) の他の問題:

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.

  1. $N \leq 600$ (up to the $15$-th test case from the top)

  2. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。