Problem Q. Half of a convex polygon

Author:T. Chistyakov, A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:24 Mb
Output file:output.txt  
Maximum points:100  

Statement

You need to divide a non-degenerate convex polygon with a horizontal line into two parts of equal area.

The polygon is specified by N vertices in the clockwise order.

Input file format

Input file contains integer N, then N pairs of floating-point numbers xi yi describing the vertices of the polygon.

Output file format

Output a single number — the ordinate of the horizontal line dividing the polygon as requested. The result must be rounded to 10-2.

Constraints

3 ≤ N ≤ 1000000

1 ≤ xi, yi ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
1 1  1 3  3 3  3 1
2

0.033s 0.007s 15