401374: GYM100425 C Tropical Stonehenge

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Tropical Stonehengetime limit per test1 secondmemory limit per test128 megabytesinputstandard inputoutputstandard output

One of the oldest existing buildings on Earth is the English Stonehenge. Nobody knows its purpose: some say it was an ancient sanctuary, other say a huge observatory. But recently, archeologists found another piece of the puzzle: an ancient tropical stonehenge.

The tropical stonegenge, unfortunately, was severely damaged by lianas. Fortunately, scientists managed to identify places of all stones of the building except one. The only thing that can help to find the position of the last stone is an ancient manuscript found nearby.

The manuscript tells the following.

  1. Tropical slonehenge is a convex polygon with N vertices with an ancient stone in each vertex.
  2. No three vertexes lie on the same straight line.
  3. All vertices have integer coordinates, the coordinates do not exceed 106.
  4. The area of the polygon is equal to S.

Knowing the coordinates of N - 1 stones and the total area S, find the coordinates of the last stone.

Input

The first line of input holds an integer number N (4 ≤ N ≤ 105) and the area of the polygon S. The area is a real number given with exactly one decimal digit (1 ≤ S ≤ 4 × 1012). The next N - 1 lines hold coordinates of the known stones in the form X Y (|X|, |Y| ≤ 106). The stones are listed in counterclockwise order of polygon traversal, excluding the missing one.

Output

Output the coordinates of the missing stone in the form X Y. It is required that the coordinates are integers and |X|, |Y| ≤ 106. In case of multiple solutions, output any one of them. It is guaranteed that the judges' inputs are constructed in such a way that there is at least one possible solution satisfying the constraints above.

ExamplesInput
4 4.0
0 0
2 0
0 2
Output
1 -2
Input
5 10.0
5 3
1 3
2 1
4 1
Output
1 5

加入题单

上一题 下一题 算法标签: