Hide

Problem D
Girðingaherping

Languages en is

A fence has been placed around the perimeter where a new building will be constructed. However, news have spread of budget cuts that are coming up, so the area for the building has to be made smaller. The mathematicians that were on call said that contractions work great for making areas smaller, so the plan was to contract the perimeter around a point until the area was halved. We will consider the perimeter to be a circular sequence of line segments. Therefore, the first and last segment are also adjacent. No two segments intersect, except for adjacent segments, which touch at their shared endpoint.

Once they started testing the procedure, they realized that it can leave some parts of the new area outside the old one, which is not an option. After lengthy talks with the geometers, a solution is suggested. The solution is to translate every line segment inward, perpendicular to its slope, by some fixed distance. The line segments then have to be lengthened or shortened accordingly so they continue to touch the adjacent line segments. Now it is simply a matter of figuring out what this fixed translation distance should be so the area is halved.

This works fine for some plans, but not others. As you translate the line segments, two of them could end up intersecting despite not being adjacent. Translations that cause two non-adjacent segments to intersect are invalid translations. Translations that cause two segments to translate through one another are invalid translations. All other translations are valid translations.

Input

The first line of input contains an integer $n$, the number of end points which define the line segments describing the perimeter, satisfying $3 \leq n \leq 5 \cdot 10^4$. The next $n$ lines contain the end points, given in counter-clockwise order around the perimeter. Each point is given as two integers, $x$ and $y$, separated by a space, satisfying $-10^9 \leq x, y \leq 10^9$, where $x$ gives the $x$-coordinate of the point and $y$ gives the $y$-coordinate of the point. No three points given in a row will be collinear.

Output

If no valid translation halves the area, print “Omogulegt!”. Otherwise, print the distance by which each line segment should be translated. Your answer will be considered correct if its absolute or relative error is at most $10^{-6}$. If there is a valid translation that halves the area there will be a translation that takes the area to $0.5 - 10^{-5}$ times the original area.

Sample Input 1 Sample Output 1
4
0 0
6828427 0
6828427 6828427
0 6828427
999999.981729615713
Sample Input 2 Sample Output 2
12
0 0
3 0
3 1
4 1
4 0
7 0
7 3
4 3
4 2
3 2
3 3
0 3
0.426092464751
Sample Input 3 Sample Output 3
12
0 0
300 0
300 125
400 125
400 0
700 0
700 300
400 300
400 175
300 175
300 300
0 300
Omogulegt!