鲍勃是一名海盗,正在寻找世界上最伟大的宝藏。宝藏位于$$$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]$$$。