Jungle Kingdom Laws#12831

Jungle Kingdom Laws

1 second
512 megabytes
Hard

The Jungle Kingdom can be represented as a convex polygon with vertices. King Lion decided to divide the kingdom into two districts and give those districts under the control of his two friends.

The laws of the Kingdom allow such a division only if the country is divided by some diagonal (a segment that connects two vertices). King wants to make the difference of the areas two districts as small as possible. Given the coordinates of the vertices of the Jingle Kingdom help him to find that difference.

Input

The first line of the input contains one integer (1 \le N \le 60\,000) — the number of the vertices in a polygon, representing the Jungle Kingdom. Each of the following lines contain two integers x_i and y_i (0 \le x_i,y_i \le 10^9) — coordinates of the next vertex of the polygon. The vertices are given in counterclockwise order. You may assume that the given polygon is strictly convex without three collinear vertices.

Output

Print one non-negative real number — the minimal non-negative absolute value of the difference of the areas of two district with absolute or relative error 10^{-9} or better.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading