P3439 [POI 2006] MAG-Warehouse

新字节城（New Byte City）的街道形成一个矩形网格——东西走向的街道称为 h 街道，南北走向的街道称为 v 街道。v 街道从西向东编号为 $1$ 到 $500\ 000\ 000$。类似地，h 街道从南向北编号为 $1$ 到 $500\ 000\ 000$。每条 v 街道与每条 h 街道相交。相邻两条 v 街道之间的距离，以及相邻两条 h 街道之间的距离，恰好为一公里。 :::align{center}  ::: 城市中有 $k$ 家商店，每家商店都位于一个十字路口。商人 Byteasar 为这 $k$ 家商店中的每一家供货，而且他每天会多次返回其中一些商店补充新鲜货物。最近他决定建造一个仓库，货物将从这里配送。出于显而易见的原因，仓库应位于一个十字路口。装载货物的卡车每次行程只能为一家商店供货——它离开仓库，将货物送到商店，然后返回仓库。卡车总是选择从仓库到商店的最短路径，以及返回的最短路径（可能是同一条）。点 $(x_i, y_i)$ 和 $(x_j, y_j)$ 之间的距离等于 $\max \{ |x_i - x_j|, |y_i - y_j| \}$。 编写一个程序： - 从标准输入读取商店的位置以及它们每日的配送次数。 - 确定一个仓库的位置，使得卡车每日行驶的总距离最小。 - 将结果写入标准输出。 给定一个网格图，其上有一堆坏点（整点，同一位置可能有多个），求一个整点，使得该整点到所有的坏点的**切比雪夫距离**之和最小。 求这个整点位置。

标准输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示新字节城中商店的数量。 接下来的 $n$ 行包含商店的描述。第 $i+1$ 行包含三个整数 $x_i$，$y_i$ 和 $t_i$（$1 \le x_i, y_i \le 5 \times 10^8$，$1 \le t_i \le 10^6$），用单个空格分隔。这个三个整数表示第 $i$ 家商店位于第 $x_i$ 条 v 街道与第 $y_i$ 条 h 街道的交叉口，卡车每天向这家商店配送 $t_i$ 次货物。

标准输出仅一行，包含两个整数 $x_m$ 和 $y_m$，用单个空格分隔，表示仓库的最佳位置为第 $x_m$ 条 v 街道与第 $y_m$ 条 h 街道的交叉口。如果存在多个最优解，输出任意一个。

感谢 @oscar 提供 SPJ。 翻译由 DeepSeek-R1 辅助完成。