SP7378 MCOMP - Manhattan Companies

众所周知，曼哈顿的街道布局独具特色。为了简化情况，我们假设街道分为水平和垂直两种类型（在地图上观察）。对于两个交叉口 A 和 B，坐标分别为 (ax, ay) 和 (bx, by)，我们定义它们的距离为 distance(A, B) = |ax - bx| + |ay - by|。 一家位于曼哈顿的公司面临这样一个挑战：需要通过快递员将 N 个交叉口连接起来，使得任意两个交叉口之间都可以通过快递员通信。我们要求在使用最少数量快递员的前提下，选择一个方案，使每位快递员负责的交叉口对中，最大距离尽可能小。

第一行输入一个整数 N，表示交叉口的数量，其中 2 ≤ N ≤ 100,000。 接下来的 N 行，每行包括两个整数 x_i 和 y_i，表示交叉口的坐标，0 ≤ x_i, y_i ≤ 100,000。

输出一个整数，表示在所有符合条件的快递员分配方案中，最大距离的最小可能值。 **本翻译由 AI 自动生成**