P26161 [AtCoder] [ARC047B] Points on a Circle
提高+
题目描述

Problem Description

There are $ N $ points on a coordinate plane.

All these points have integer values for both their $ x $ and $ y $ coordinates, meaning they are on lattice points.

It is known that all these points have the same Manhattan distance to a certain point $ P $. Here, the Manhattan distance is the distance calculated by $|\ a-c\ |\ +\ |\ b-d\ |$ when the coordinates of two points are $(a,\ b)$ and $(c,\ d)$, respectively.

And, point $ P $ is also on a lattice point.

Please list one possible point $ P $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ : $ x_N $ $ y_N $

  • The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 10^5)$ representing the number of points.
  • The next $ N $ lines contain two integers $x_i,\ y_i(-10^9\ ≦\ x_i,\ y_i\ ≦\ 10^9)$ representing the coordinates of the $ i $th point.
  • $(x_i,\ y_i)\ ≠\ (x_j,\ y_j)$ holds if $i\ ≠\ j$.
  • All $ N $ points are guaranteed to have the same Manhattan distance from a certain point.

Output Format

Output the $ x $ coordinate value $ Px $ and the $ y $ coordinate value $ Py $ of a possible point $ P $ in one line separated by a space.

In this case, $-10^9\ ≦\ Px,\ Py\ ≦\ 10^9$ must hold (it is guaranteed that such a solution exists).

End the output with a newline.

Sample Input and Output

Sample Input #1

3
1 2
3 4
2 5

Sample Output #1

2 3

Sample Input #2

3
0 1
1 0
-1 0

Sample Output #2

0 -2016

Notes/Hints

Sample Explanation 1

All given points have a Manhattan distance of $ 2 $ from the point $(2,\ 3)$.

Sample Explanation 2

Any point $(0,\ y)$ where $y\ ≦\ 0$ satisfies the conditions for point $ P $. As long as $-10^9\ ≦\ y$, any of them can be output.

输入格式

见题面 Input 部分

输出格式

见题面 Output 部分

样例输入
3 1 2 3 4 2 5
样例输出
2 3