题解：花神的浇花集会

核心问题

给定平面上 $n$ 个点 $(x_i, y_i)$，要找一个点 $(X, Y)$ 使得： [ \sum_{i=1}^n \max(|X - x_i|, |Y - y_i|) ] 最小，其中 $X, Y \in [0, 10^5]$ 且为整数。

思路分析

$\max(|X-x_i|, |Y-y_i|)$ 是切比雪夫距离（Chebyshev distance）。
切比雪夫距离可以通过坐标变换转化为曼哈顿距离（Manhattan distance）：

变换公式： [ (u_i, v_i) = (x_i + y_i, x_i - y_i) ] 则原问题中 [ \max(|X-x_i|, |Y-y_i|) = \frac{|U - u_i| + |V - v_i|}{2} ] 其中 [ U = X + Y, \quad V = X - Y ]

算法步骤

1. 将每个点 $(x_i, y_i)$ 变换为 $(u_i, v_i) = (x_i + y_i, x_i - y_i)$。
2. 原问题转化为：求 $(U, V)$ 使 $\sum |U - u_i| + \sum |V - v_i|$ 最小。
3. 曼哈顿距离的中位数性质：使 $\sum |U - u_i|$ 最小的 $U$ 是 $u_i$ 的中位数；同理 $V$ 是 $v_i$ 的中位数。
4. 取中位数：对 $u$ 数组和 $v$ 数组分别排序，取中位数候选。
5. 逆变换回 $(X, Y)$ 需注意奇偶性：$X = \frac{U+V}{2}$，$Y = \frac{U-V}{2}$ 需为整数，因此 $U$ 和 $V$ 必须同奇偶。
6. 如果中位数组合 $(U, V)$ 奇偶不同，则需检查相邻的四个点（曼哈顿距离最近的点）来找到最小和。

时间复杂度

• 排序 $O(n \log n)$
• 计算中位数 $O(n)$
• 总复杂度 $O(n \log n)$，可以处理 $n \le 10^5$ 的数据规模。

关键点

• 利用切比雪夫到曼哈顿的坐标变换简化问题
• 曼哈顿距离的最小化可通过中位数实现
• 注意逆变换时的整数约束，可能需要微调候选点
• 最终答案除以 2 是因为变换中的 1/2 因子