Prime Cut 3

Wahoo!

It's a me, Mario! I need you to help me win a round of Mario Party Jamboree (TM).

I have to play a minigame with my bro, Luigi, called Prime cut. In this game I get a steak and cut it in 2 equal portions, can you find a cut for me?

The steak is a 2d convex polygon (no internal angle is greater than 180 degrees). You have to find the value of $a$ such that the line x=$a$ cuts the steak into 2 pieces of equal size. In other words, you have to find the vertical line that splits the steak into 2 halves.

Input

The first line has one integer, $n$, the number of points in the steak The next $n$ lines each have 2 integers, $x_i$ $y_i$, the x and y value of the ith point.

• $-1e4 \le x_i, y_i \le 1e4$
• $1000 \le n \le 1e5$

It is guaranteed that no 3 successive points in the the steak are collinear, or form an internal angle greater than 180 degrees. All points are distinct.

Output:

Give me the x-value of the line that divides the steak in 2. Answers within 1e-3 will be accepted.

Sample Input:

3
0 0
1 1
0 1

Sample Output:

0.2928931713

Sample Input:

4
1 1
3 1
3 4
1 4

Sample Output:

2

Sample Input:

5
0 0
1 0
1 1
0 2
-1 1

Sample Output:

0.1291712523