当前没有测试数据。

这一次我们将背景设定在初中数学中非常重要的平面直角坐标系与距离度量。

这道题目考察的是中位数性质、前缀和优化以及曼哈顿距离的性质。难度定位在 GESP 5级（约等于 CSP-J T2/T3 难度）。

题目：最佳校区选址（Optimal Campus Selection）

【背景知识讲解】

在初中数学八年级下册中，我们学习了平面直角坐标系。在实际生活中，两点间的距离并不总是能走直线（欧几里得距离）。

1. 曼哈顿距离（Manhattan Distance）：在一个像棋盘方格一样的城市街区中，从点 $A(x_1, y_1)$ 到点 $B(x_2, y_2)$ 的行走路径只能是水平或垂直的。因此，两点间的曼哈顿距离定义为：$$D = |x_1 - x_2| + |y_1 - y_2|$$
2. 绝对值不等式性质：在数轴上，若要找一个点 $x$，使得它到其他 $N$ 个已知点的距离之和 $\sum |x - x_i|$ 最小，这个点 $x$ 应该是这组数据的中位数。
3. 独立性：在平面上，曼哈顿距离的 $x$ 分量和 $y$ 分量是互不干扰的。要使总距离之和最小，可以分别处理 $x$ 轴和 $y$ 轴。

【题目描述】

某地区教育局准备在现有的 $N$ 所学校中，选定其中一所作为“中心校区”，用于举办大型数学竞赛。 为了公平起见，教育局希望选出的这所学校，到其他所有 $N-1$ 所学校的曼哈顿距离之和最小。

如果有多个学校满足距离之和最小的条件，请选择编号最小的那一所（学校编号按输入顺序从 $1$ 到 $N$）。

【输入格式】

第一行包含一个整数 $N$，表示学校的数量。 接下来 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 所学校的坐标。

【输出格式】

输出一行，包含两个整数：所选学校的编号以及该学校到其他所有学校的曼哈顿距离之和。

【样例数据】

输入：

3
1 1
2 2
3 3

输出：

2 4

样例解释：

• 选择 1 号学校 (1,1)：距离和 $= (|1-2|+|1-2|) + (|1-3|+|1-3|) = 2 + 4 = 6$。
• 选择 2 号学校 (2,2)：距离和 $= (|2-1|+|2-1|) + (|2-3|+|2-3|) = 2 + 2 = 4$。
• 选择 3 号学校 (3,3)：距离和 $= (|3-1|+|3-1|) + (|3-2|+|3-2|) = 4 + 2 = 6$。 最优点为 2 号学校，距离和为 4。

【数据范围】

• 对于 100% 的数据：$1 \le N \le 100,000$。
• 坐标范围：$-10^9 \le x_i, y_i \le 10^9$。
• 结果可能很大，请使用 long long 存储距离和。

一、 思路提示

1. 暴力法的瓶颈： 计算一个点到其他所有点的距离需要 $O(N)$。如果有 $N$ 个点，总时间复杂度是 $O(N^2)$。当 $N=10^5$ 时，计算量为 $10^{10}$，会超时。
2. 分维度处理： 总距离 $S = \sum |x_{target} - x_i| + \sum |y_{target} - y_i|$。我们可以分别计算 $x$ 轴的总距离和 $y$ 轴的总距离。
3. 快速求和技巧（前缀和）： 假设我们已经把所有 $x$ 坐标从小到大排序。 对于第 $k$ 小的坐标 $x_k$，它左边有 $k-1$ 个点，右边有 $N-k$ 个点。
   • 到左边点的距离和：$x_k \times (k-1) - (\text{左边所有点的和})$。
   • 到右边点的距离和：$(\text{右边所有点的和}) - x_k \times (N-k)$。 通过前缀和数组，我们可以在 $O(1)$ 时间内算出这两部分的和。

二、 预备知识点总结

1. 结构体与排序：记录原始编号，并对坐标进行排序。
2. 前缀和（Prefix Sum）：用于 $O(1)$ 快速计算区间和。
3. 曼哈顿距离性质：理解 $x, y$ 轴可以独立计算。
4. 数据类型：理解为何坐标差的累加需要用 long long（最高可达 $10^{14}$ 级别）。

三、 启发式教学：草稿纸上的推理过程

教练：“同学们，先看一维的情况。你在一条直线上有 5 个点：1, 2, 4, 10, 20。如果你站在 4 这个位置，怎么快速算出你到其他人的距离？”

1. 分类讨论：
   • 左边的点：1, 2。距离 = $(4-1) + (4-2) = 2 \times 4 - (1+2)$。
   • 右边的点：10, 20。距离 = $(10-4) + (20-4) = (10+20) - 2 \times 4$。
2. 推广到公式：
   • 如果我们提前算出前缀和 sum[i] = x[1] + ... + x[i]。
   • 站在第 $k$ 个点上，总距离 $D_x = [ (k-1) \cdot x_k - sum[k-1] ] + [ (sum[N] - sum[k]) - (N-k) \cdot x_k ]$。
3. 回到二维：
   • 对 $x$ 坐标排个序，算出每个原始编号在 $x$ 轴上的贡献。
   • 对 $y$ 坐标排个序，算出每个原始编号在 $y$ 轴上的贡献。
   • 注意：同一个学校在 $x$ 轴排序后是第 3 名，在 $y$ 轴排序后可能是第 1 名。所以我们要用原始编号把两份贡献加起来。

四、 读题关键词总结

1. “曼哈顿距离” $\rightarrow$ 暗示 $x$ 和 $y$ 可以分开处理。
2. “现有学校中选一个” $\rightarrow$ 目标点必须是输入给出的点之一。
3. “编号最小” $\rightarrow$ 更新 min_dist 时注意判断条件。
4. $N=100,000$ $\rightarrow$ 必须使用 $O(N \log N)$ 排序 + $O(N)$ 扫描。