题目描述

“地段，地段，还是地段”是房地产和商业中常用的一句话，用来强调房产或商业实体物理位置的重要性。在房地产领域，这句话表明房产的吸引力和价值很大程度上受其地理位置的影响，通常比房产本身的特性或状况更为重要。在商业领域，这句话强调零售店或商业机构的成功可能会因其地理位置而受到显著影响。

近年来，人们倾向于购买电动汽车，但购车者很快发现，在公寓或住宅中安装充电桩非常困难。建设充电站可能是一个赚钱的好主意。你的老板莉娜让你为她的充电站找到一个合适的位置，以服务电动汽车车主。

你得到了一个包含 $n$ 个位置的列表，每个位置以二维平面上的坐标 $(x, y)$ 表示。每个位置都是一处没有充电基础设施的公寓或住宅。你的任务是在一个位置建造充电站，使得该位置到列表中所有 $n$ 个位置的曼哈顿距离之和最小。在本问题中，距离使用曼哈顿距离度量。两点 $(x_1, y_1)$ 与 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。你的目标是找到一个位置 $(x, y)$，使得该位置到列表中所有 $n$ 个位置的曼哈顿距离之和最小。

输入格式

第一行包含一个正整数 $n$，表示位置的数量。接下来的 $n$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个位置的坐标为 $(x_i, y_i)$。

输出格式

输出位置 $(x, y)$，使得 $(x, y)$ 到列表中所有 $n$ 个位置的曼哈顿距离之和最小。如果存在多个解，则输出使 $x$ 最小的解；如果仍有多个解，则输出使 $y$ 最小的解。

4
3 1
0 2
2 3
1 0

1 1

2
0 0
2 2

0 0

提示

• $1 \leq n \leq 100000$
• $-100000 \leq x_i \leq 100000$，对于 $1 \leq i \leq n$
• $-100000 \leq y_i \leq 100000$，对于 $1 \leq i \leq n$

翻译由 DeepSeek V3.2 完成