Prime Cut 3

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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

Comments

There are no comments at the moment.