Simple Hull
Gary has been trying to generate simple orthogonal polygons for his geometry homework, but his algorithm seems to be having some issues. After some good hours of debugging, he finally realized what is the problem: apparently, the polygons that he was generating may contain self-intersections, which was not at all what he intended!
More specifically, the “polygons” that Gary has generated are represented by a list of n points p[i] = (x[i], y[i]), forming a closed polygonal chain. The polygonal chain may contain self-intersections. The segments formed by every two consecutive points (x[i], y[i]) and (x[j], y[j]) in the chain are either vertical or horizontal.
The polygonal chains for the example test cases are illustrated below (not to scale):
You have decided to help Gary fix this issue, by computing a simple (not self-intersecting) polygon with vertical and horizontal segments that fully contains the chain, and its area is as small as possible. What is the area of such a polygon?
Formally, you have to compute the infimum of the areas of all simple orthogonal polygons that contain all the segments [p[i], p[j]], for every two adjacent points p[i] and p[j].
Input
The first line will contain a positive integer n (4 ≤ n ≤ 100 000). The following n lines will contain the points (x[i], y[i]) in order (1 ≤ x[i], y[i] ≤ 10^6). No two consecutive points coincide, and there are no two consecutive vertical segments or two consecutive horizontal segments.
Output
Output a single non-negative integer, the infimum of the areas of all simple polygons that enclose the closed polygonal chain. It can be proven that the answer is always integer.
Example
In examples 1 and 3 there are no simple polygons with areas exactly equal to 50 and 8, respecively; however, there exist simple polygons with areas arbitrarily close to these values.