Polygon Shrinking Kit

A Polygon Shrinking Kit is a tool used often in the geometric magic classes of Nlogonia. The kit consists of two points $A$ and $B$ in the Cartesian plane.

Consider a convex polygon given by the vertices $1, 2, \ldots, N$, in this order. Shrinking this polygon with the kit must follow some rules. Each vertex $x$ of the polygon is moved exactly once: either to the midpoint of segment $Ax$ or to the midpoint of segment $Bx$. The shrinking must produce a new convex polygon that preserves the relative order of the vertices of the original polygon. In other words, among all possible ways to apply the kit, only those whose final sequence of vertices $1, 2, \ldots, N$ forms a convex polygon are valid. The original convex polygon may be clockwise while a valid shrinking produces a counterclockwise convex polygon with the same vertex order. Only the relative order of the points matters, not the orientation.

In this problem, the moved points $Q_1, Q_2, \ldots, Q_N$ form a convex polygon in this order when all of the following hold (take $Q_{N+1} = Q_1$ and $Q_0 = Q_N$):

1. For every $i$, the neighboring points $Q_i$ and $Q_{i+1}$ are different.
2. At every vertex $Q_i$, the boundary turns in the same direction (all left turns or all right turns) or goes straight on. Going straight on means that $Q_{i-1}$, $Q_i$, $Q_{i+1}$ lie on one line and $Q_i$ lies between the other two. Turning back along a line is not allowed.
3. The boundary goes around exactly once. That is, the result is a simple polygon that does not cross itself.

A single point or a line is not a polygon. So if a use of the kit produces anything other than a convex polygon, that use is not valid.

Geometric magic is a hard subject for most students. The teacher gave the students a convex polygon and asked them to shrink it with the kit so that its area is as small as possible, and a friend of yours begged you to solve the task for him. Find the minimum area of a polygon that a valid use of the kit can produce.

The figure above shows a valid use of the kit. The shaded polygon has the smallest area among the polygons that preserve the vertex order, and points $A$ and $B$ are the two points of the kit. Despite the name, the kit can sometimes make a polygon larger. Geometry is hard!

The first line contains an integer $N$, the number of vertices of the polygon. Each of the next $N$ lines contains two integers $x$ and $y$, the coordinates of a vertex. The last line contains four integers $A_x$, $A_y$, $B_x$, $B_y$: the $x$ and $y$ coordinates of $A$, then the $x$ and $y$ coordinates of $B$.

The vertices are given in the order in which they appear on the polygon, clockwise or counterclockwise. No point appears twice, and the given polygon is convex in the sense defined above. Three consecutive vertices may lie on one line.

Constraints

• $3 \le N \le 10^5$
• $-10^6 \le x, y \le 10^6$
• $-10^6 \le A_x, A_y, B_x, B_y \le 10^6$

Print one line with the minimum area of a polygon that a valid use of the kit can produce, with exactly 3 digits after the decimal point.

Moving every vertex to the midpoint of segment $Ax$ gives a translated copy of the original polygon scaled by one half, so a valid use always exists. Every moved point has coordinates that are halves of integers, so the area is always a multiple of $\frac{1}{8}$. The answer is therefore exact with 3 decimal digits, and no rounding is needed.