[AdditionalFile5498.zip](file://AdditionalFile5498.zip?type=additional_file)

#5498. 「POI2006 R2」仓库 Warehouse

标签: 传统 | 时间限制: 500 ms | 内存限制: 32 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – II etap Magazyn

字节市（Bajtomieście）的街道形成了一个垂直的网格——街道要么是东西向，要么是南北向。南北向的街道从西到东依次编号为 $1$ 至 $500000000$。同样，东西向的街道从南到北依次编号为 $1$ 至 $500000000$。每条南北向的街道都与每条东西向的街道相交，反之亦然。相邻的两条南北向街道之间，以及相邻的两条东西向街道之间的距离均为一公里。

市内有 $k$ 家商店，每家商店都位于一个街道的十字路口。商人 Bajtazar 负责为这 $k$ 家商店供货，其中有些商店他每天需要去好几次。Bajtazar 决定建造一个仓库，并从那里向各商店配送货物。这个仓库也必须建在街道的十字路口。负责送货的卡车在单次行程中只能访问一家商店——它从仓库出发，将货物送到商店，然后返回仓库。卡车总是沿着从仓库到商店以及返回的最短路线行驶。点 $(x_i, y_i)$ 和 $(x_j, y_j)$ 之间的距离等于：

$$\max \left\{\left|x_{i}-x_{j}\right|,\left|y_{i}-y_{j}\right|\right\}$$

请编写一个程序，实现以下功能：

• 从标准输入读取商店的布局以及每天向各商店送货的次数，
• 确定一个仓库的位置，使得卡车每天行驶的总距离最小，
• 将结果输出到标准输出。

输入格式

输入的第一行包含一个整数 $n$ $(1 \le n \le 100000)$，表示字节市的商店数量。

接下来的 $n$ 行是商店的描述。第 $i+1$ 行包含三个整数 $x_i, y_i, t_i$ $(1 \le x_i, y_i \le 500000000, 1 \le t_i \le 1000000)$，由单个空格隔开。这表示第 $i$ 家商店位于第 $x_i$ 条南北向街道和第 $y_i$ 条东西向街道的交叉口，并且卡车每天到这家商店送货 $t_i$ 次。

输出格式

输出的第一行且仅一行应包含两个整数 $x_m$ 和 $y_m$，由单个空格隔开，描述仓库的位置，即位于第 $x_m$ 条南北向街道和第 $y_m$ 条东西向街道的交叉口。如果存在多个正确答案，你的程序可以输出其中任意一个。

样例

输入

3
2 2 1
6 2 1
4 6 1

输出

4 4

下图展示了样例输入中的情况。带编号的点表示相应的商店。点 M 表示仓库的位置。