Atcoder ABC 330 - Minimize Bounding Square

题目描述

在平面上有标记为1,2，…，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，代表N个点，最多K次操作

第2-N+1行，代表N个点的坐标x，y

数据范围

• 1≤N≤2×10^5
• 0≤K≤4×10^14
• 0≤Xi​,Yi​≤10^9

输出描述

输出可能的最小正方形边长

提示

样例1解释：

如图所示：

在按照图中的箭头执行四次移动后，可以把所有的点集中在边长为3的正方形内，并且在k次移动限制内该值最小。