Minimize Bounding Square

题目描述

平面上有标号为 $1, 2, \dots, N$ 的 $N$ 个点。点 $i$ 位于坐标 $(X_i, Y_i)$。
你可以执行以下操作，执行次数介于 $0$ 到 $K$ 次（含）之间。

首先，选择这 $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)$。

允许多个点位于相同坐标。注意输入中也可能已有多个点位于相同坐标。

在所有操作结束后，画一个边与 $x$ 轴或 $y$ 轴平行的正方形，使得该正方形包含所有 $N$ 个点（点可以在正方形内部或边上）。
求该正方形边长的最小可能值。由于所有点始终位于格点，该值可以证明为整数。 特别地，如果所有点可以通过操作移动到相同坐标，则答案记为 $0$。

输入格式

输入从标准输入给出，格式如下： $N$ $K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

输出格式

输出一个整数，为答案。

6 5
2 0
5 2
0 3
3 2
3 4
1 5

3

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

0

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

484373824

提示

所有输入值都是整数。 $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$下图用横向的 $x$ 轴和纵向的 $y$ 轴说明了该情况。 例如，按照图中箭头所示进行四次移动后，你可以包含所有点的正方形（图中所示）的边长为 $3$，且可以证明这是最小值。
所有点从一开始就已存在于相同坐标。
例如，通过执行零次操作，所有点可以被使得存在于相同坐标，因此该输入的答案为 $0$。

标签: AtCoder|abc330F

来源

AtCoder|abc330F