103305: [Atcoder]ABC330 F - Minimize Bounding Square
Description
Score : $525$ points
Problem Statement
There are $N$ points labeled $1, 2, \dots, N$ on the $xy$-plane. Point $i$ is located at coordinates $(X_i, Y_i)$.
You can perform the following operation between $0$ and $K$ times, inclusive.
- First, choose one of the $N$ points. Let $k$ be the selected point, and assume it is currently at $(x, y)$.
- Next, choose and execute one of the following four actions:
- Move point $k$ along the $x$-axis by $+1$. The coordinates of point $k$ become $(x+1, y)$.
- Move point $k$ along the $x$-axis by $-1$. The coordinates of point $k$ become $(x-1, y)$.
- Move point $k$ along the $y$-axis by $+1$. The coordinates of point $k$ become $(x, y+1)$.
- Move point $k$ along the $y$-axis by $-1$. The coordinates of point $k$ become $(x, y-1)$.
- It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates.
After all your operations, draw one square that includes all the $N$ points inside or on the circumference, with each side parallel to the $x$- or $y$-axis.
Find the minimum possible value for the length of a side of this square. This value can be shown to be an integer since all points are always on lattice points.
In particular, if all points can be made to exist at the same coordinates, the answer is considered to be $0$.
Constraints
- All input values are integers.
- $1 \le N \le 2 \times 10^5$
- $0 \le K \le 4 \times 10^{14}$
- $0 \le X_i, Y_i \le 10^9$
Input
Input is given from Standard Input in the following format:
$N$ $K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$
Output
Print the answer as an integer.
Sample Input 1
6 5 2 0 5 2 0 3 3 2 3 4 1 5
Sample Output 1
3
The figure below illustrates this case with the horizontal $x$-axis and the vertical $y$-axis.
For example, after performing four moves following the arrows in the figure, you can include all points inside or on the circumference of the square shown in the figure with a side length of $3$, and this can be shown to be the minimum value.
Sample Input 2
4 400000000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 2
0
All points already exist at the same coordinates from the beginning.
For example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is $0$.
Sample Input 3
10 998244353 489733278 189351894 861289363 30208889 450668761 133103889 306319121 739571083 409648209 922270934 930832199 304946211 358683490 923133355 369972904 539399938 915030547 735320146 386219602 277971612
Sample Output 3
484373824
Output
分数：$525$ 分
问题描述
在 $xy$ 平面上标有 $N$ 个点，分别标记为 $1, 2, \dots, N$。点 $i$ 位于坐标 $(X_i, Y_i)$。
- 首先，从 $N$ 个点中选择一个。令 $k$ 为选择的点，假设它当前位于 $(x, y)$。
- 其次，从以下四种操作中选择并执行一个：
- 将点 $k$ 沿 $x$ 轴向右移动 $1$ 个单位。点 $k$ 的坐标变为 $(x+1, y)$。
- 将点 $k$ 沿 $x$ 轴向左移动 $1$ 个单位。点 $k$ 的坐标变为 $(x-1, y)$。
- 将点 $k$ 沿 $y$ 轴向上移动 $1$ 个单位。点 $k$ 的坐标变为 $(x, y+1)$。
- 将点 $k$ 沿 $y$ 轴向下移动 $1$ 个单位。点 $k$ 的坐标变为 $(x, y-1)$。
- 允许多个点在同一坐标处。请注意，输入可能已经包含多个点在同一坐标处。
执行完所有操作后，在包含所有 $N$ 个点的内部或圆周上的正方形中画出一个正方形，每边平行于 $x$ 或 $y$ 轴。
找到这个正方形边长的最小可能值。由于所有点始终在格点上，所以这个值可以证明是整数。
特别是，如果可以将所有点都放在相同的坐标上，则答案被认为是 $0$。
约束条件
- 所有输入值都是整数。
- $1 \le N \le 2 \times 10^5$
- $0 \le K \le 4 \times 10^{14}$
- $0 \le X_i, Y_i \le 10^9$
输入格式
输入从标准输入按以下格式给出：
$N$ $K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$
输出格式
将答案作为整数打印。
样例输入 1
6 5 2 0 5 2 0 3 3 2 3 4 1 5
样例输出 1
3
下图中的水平线表示 $x$ 轴，垂直线表示 $y$ 轴。
例如，在按照图中的箭头执行四次移动后，可以将所有点包含在图中所示的边长为 $3$ 的正方形内或圆周上，可以证明这是最小值。
样例输入 2
4 400000000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
样例输出 2
0
从一开始就存在多个点在相同的坐标处。
例如，通过执行零次操作，可以将所有点放在相同的坐标处，因此此输入的答案为 $0$。
样例输入 3
10 998244353 489733278 189351894 861289363 30208889 450668761 133103889 306319121 739571083 409648209 922270934 930832199 304946211 358683490 923133355 369972904 539399938 915030547 735320146 386219602 277971612
样例输出 3
484373824