← 返回题目列表

Codeforces · 1091/B

B. 新年与宝藏地理定位

中文机器翻译题面 查看原题

鲍勃是一名海盗,正在寻找世界上最伟大的宝藏。宝藏位于$$$T$$$点,坐标待查。

鲍勃环游世界并在 $$$n$$$ 方尖碑上收集了宝藏位置的线索。这些线索是古文,他只是在家里解密。由于他不知道哪条线索属于哪个方尖碑,因此找到宝藏可能会带来挑战。你能帮助他吗?

众所周知,世界是一个二维平面。第 $$$i$$$ 方尖碑位于整数坐标 $$$(x_i, y_i)$$$ 处。第 $$$j$$$ 线索由 $$$2$$$ 整数 $$$(a_j, b_j)$$$ 组成,属于方尖碑 $$$p_j$$$,其中 $$$p$$$ 是 $$$n$$$ 元素的一些(未知)排列。这意味着宝藏位于$$$T=(x_{p_j} + a_j, y_{p_j} + b_j)$$$。这一点$$$T$$$对于所有线索都是一样的。

换句话说,每条线索都属于其中一个方尖碑,而每个方尖碑也恰好有一条属于它的线索。一条线索代表从方尖碑到宝藏的向量。线索必须分布在方尖碑中,使它们都指向宝藏的同一位置。

你的任务是找到宝藏的坐标。如果有多个解决方案,您可以打印其中任何一个。

请注意,您不需要找到排列。排列仅用于解释问题。

输入

第一行包含一个整数 $$$n$$$($$$1 \leq n \leq 1000$$$)——方尖碑的数量,也等于线索的数量。

接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$-10^6 \leq x_i, y_i \leq 10^6$$$) - 第 $$$i$$$ 方尖碑的坐标。所有坐标都是不同的,即 $$$x_i \neq x_j$$$ 或 $$$y_i \neq y_j$$$ 将满足每个 $$$(i, j)$$$ 使得 $$$i \neq j$$$。

接下来的 $$$n$$$ 行包含两个整数 $$$a_i$$$、$$$b_i$$$ ($$$-2 \cdot 10^6 \leq a_i, b_i \leq 2 \cdot 10^6$$$) — 第 $$$i$$$ 线索的方向。所有坐标都是不同的,即 $$$a_i \neq a_j$$$ 或 $$$b_i \neq b_j$$$ 将满足每个 $$$(i, j)$$$ 使得 $$$i \neq j$$$。

保证存在一个排列$$$p$$$,使得对于所有$$$i,j$$$,它保持$$$\left(x_{p_i} + a_i, y_{p_i} + b_i\right) = \left(x_{p_j} + a_j, y_{p_j} + b_j\right)$$$。

输出

输出一行包含两个整数 $$$T_x, T_y$$$ — 宝藏的坐标。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

2
2 5
-6 4
7 -2
-1 -3

输出 #1

1 2

输入 #2

4
2 2
8 2
-7 0
-2 6
1 -14
16 -12
11 -18
7 -14

输出 #2

9 -12

注意

由于$$$n = 2$$$,我们可以考虑两个元素的所有排列。

如果$$$p = [1, 2]$$$,则方尖碑$$$(2, 5)$$$持有线索$$$(7, -2)$$$,这意味着宝藏隐藏在$$$(9, 3)$$$处。第二个方尖碑 $$$(-6, 4)$$$ 会给出线索 $$$(-1,-3)$$$ 和 $$$(-7, 1)$$$ 处的宝藏。然而,两个方尖碑必须给出相同的位置,因此这显然不是正确的排列。

如果隐藏排列为 $$$[2, 1]$$$,则第一条线索属于第二个方尖碑,第二条线索属于第一个方尖碑。因此 $$$(-6, 4) + (7, -2) = (2,5) + (-1,-3) = (1, 2)$$$,所以 $$$T = (1,2)$$$ 是宝藏的位置。

在第二个示例中,隐藏排列为 $$$[2, 3, 4, 1]$$$。