P15602 [ICPC 2020 Jakarta R] Police Stations

在扁平之地有 $N$ 个警察局，第 $i$ 个警察局位于坐标 $(x_i, y_i)$ 处。当局计划通过减少它们之间经常出现的沟通不畅来增强这些警察局之间的协同作用。为此，当局决定建造一个新的塔楼，作为通信控制中心（CCC）。注意，CCC 只能建在 $(x, y)$ 处，其中 $x$ 和 $y$ 均为整数。$(x, y)$ 处是否已经有一个警察局并不重要；CCC 可以与那个警察局建在一起。 然后，CCC 将向每个警察局铺设通信电缆，并有一些限制。 - 每条电缆仅为一个警察局服务，因此，要为 $N$ 个警察局服务，需要 $N$ 条电缆。 - 电缆只能平行于 $x$ 轴和 $y$ 轴铺设；不允许对角线交叉。 由于扁平之地某些奇怪的物理定律，每条电缆在 $x$ 轴方向上的长度最多只能为 $L$，在 $y$ 轴方向上的长度最多只能为 $W$；这就是为什么这种电缆在扁平之地被称为 $(L, W)$ 电缆。为了保持通信稳定，所有警察局都应使用相同类型的电缆连接。 扁平之地最近的科技进展使得物理学家能够以一定的成本制造任意 $L$ 和 $W$ 的 $(L, W)$ 电缆。由于 $L$ 和 $W$ 越大成本越高，当局需要找出能够满足需求的 $L$ 和 $W$，即用 CCC 连接所有警察局，同时最小化 $L + W$ 的值。 你的任务是找到 $L$ 和 $W$，使得 $L + W$ 的值最小，并且当局可以将 CCC 建在 $(x, y)$ 处（$x$ 和 $y$ 均为整数），同时所有警察局都能用 $(L, W)$ 电缆连接到 CCC。如果有多个解，首先最小化 $L$，然后最小化 $W$。

输入第一行包含一个整数 $N$（$1 \leq N \leq 100\,000$），表示扁平之地的警察局数量。接下来 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$-10^6 \leq x_i, y_i \leq 10^6$），表示每个警察局的位置。

输出一行两个整数（中间用一个空格分隔），分别为 $L$ 和 $W$，使得 $L + W$ 的值最小，并且当局可以将 CCC 建在 $(x, y)$ 处（$x$ 和 $y$ 均为整数），同时所有警察局都能用 $(L, W)$ 电缆连接到 CCC。如果有多个解，首先最小化 $L$，然后最小化 $W$。

#### 样例 #1 解释 当局可以做出的最优决策是将 CCC 建在 $(40, 30)$，并准备 $\langle 50, 60 \rangle$ 电缆以将所有警察局连接到 CCC。 #### 样例 #2 解释 为了使 $L + W$ 最小，CCC 必须建在 $(121, 744)$ 或 $(121, 745)$。无论哪种方式，他们都需要 $\langle 1, 5 \rangle$ 电缆来将两个警察局连接到 CCC。 #### 样例 #3 解释 当局可以做出的最优决策是将 CCC 建在 $(31, 30)$，并准备 $\langle 61, 50 \rangle$ 电缆以将所有警察局连接到 CCC。 翻译由 DeepSeek 完成