URI Online Judge | 2245

Shrinking Polygons Kit

By Maratona de Programação da SBC 2016 BR Brazil

Timelimit: 1

A Polygon Shrinkage Kit is a widely used material in geometrical magic classes at Nlogonia. The kit consists of two points A and B in the Cartesian plane. Consider a convex polygon given by the vertices 1, 2 ... N, in that order. To shrink this polygon using the kit, some rules must be respected. X Each vertex of the polygon must be moved only once: at the midpoint of the segment Ax or Bx the midpoint of the segment. The shrinking operation is to produce a new convex polygon that preserves the relative order of vertices of the original polygon. In other words, considering all possible ways of applying the kit, only those whose final sequence of vertices 1, 2 ... N is a convex polygon are valid. See the original convex polygon can be clockwise and a valid shrink operation takes a convex polygon in counter-clockwise, in the order of the vertices. Only the relative order of the points is important, not the meaning.

It is known that geometrical magic is not the forte of most students. The teacher asked them to use the shrinking kit to shrink a convex polygon provided by it in order to obtain the smallest possible area and a friend begged her to you to solve the issue for him. Answer the smallest possible area of ​​the polygon for it.

The above figure illustrates a valid use of the kit, where the shaded polygon is the smallest possible area that preserves the order of the vertices. Points A and B correspond to the kit points. Note that, despite the shrinkage name, it is sometimes possible to use the kit to increase the area of ​​the polygons! As geometry is hard!

Note that a single point or a line are not considered polygons. Therefore, a use of kit produced as a result of a somewhat different convex polygon, this is not a valid use.


The first line of input contains an integer N (3 ≤ N ≤ 105), the Number, polygon vertices. Here N rows, each of two integers x, y (-106x, y ≤ 106), the vertices of the polygon. The last line of input contains four integers, Ax, Ay, Bx e By (-106Ax, Ay, Bx, By ≤ 106), the x and y coordinates of A and the x and y coordinates of B, respectively. The entry points will be given in the correct order in which they appear in the polygon, clockwise or counterclockwise. There will be no repeated points and the polygon is convex.


Its program should produce a line containing a real number with 3 decimal places of precision, representing the smallest area possible for a polygon obtained using the kit.

Input Samples Output Samples

20 6
4 8
2 6
0 0 4 0


0 4
4 4
0 0
3 -2 -3 -2


0 4
4 4
0 0
2 -2 -2 -2