AT_abc330_f [ABC330F] Minimize Bounding Square

题目描述

在 $xy$ 平面上有 $N$ 个点，编号为 $1,2,\dots,N$。其中第 $i$ 个点的坐标为 $(X_i,Y_i)$。
你可以进行如下操作 $0$ 次或至多 $K$ 次：

• 首先，从 $N$ 个点中选择一个。设选中的点为 $k$，其当前坐标为 $(x,y)$。
• 然后，从以下 $4$ 种操作中选择一种并执行：
  • 将点 $k$ 沿 $x$ 轴正方向移动 $1$ 单位，坐标变为 $(x+1,y)$。
  • 将点 $k$ 沿 $x$ 轴负方向移动 $1$ 单位，坐标变为 $(x-1,y)$。
  • 将点 $k$ 沿 $y$ 轴正方向移动 $1$ 单位，坐标变为 $(x,y+1)$。
  • 将点 $k$ 沿 $y$ 轴负方向移动 $1$ 单位，坐标变为 $(x,y-1)$。
• 允许多个点重叠在同一坐标上。请注意，输入中也可能有多个点初始就在同一坐标。

所有操作结束后，请画出一个正方形，使得 $N$ 个点全部被包含在该正方形的内部或边界上，且正方形的每条边都平行于 $x$ 轴或 $y$ 轴。
请你求出该正方形可能的最小边长。由于所有点始终位于整数格点上，可以证明该最小边长一定为整数。

特别地，如果可以将所有点移动到同一坐标，则答案为 $0$。

输入格式

输入按以下格式从标准输入读入。

$N$ $K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

输出格式

请输出一个整数，表示所求的最小正方形边长。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $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$

样例解释 1

本样例中，横轴为 $x$ 轴，纵轴为 $y$ 轴，示意图如下：

例如，按照图中的箭头移动 $4$ 次后，可以用边长为 $3$ 的正方形将所有点包含在内，并且这是最小值。

样例解释 2

所有点一开始就在同一坐标。例如不进行任何操作（即操作 $0$ 次），即可让所有点重合，因此本输入的答案为 $0$。

由 ChatGPT 4.1 翻译