2020 SEERC

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 pi = (xi, yi), forming a closed polygonal chain. The polygonal chain may contain self-intersections. The segments formed by every two consecutive points (xi, yi) and (xj, yj) 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 [pi, pj], for every two adjacent points pi and pj.


The first line will contain a positive integer n (4n100 000). The following n lines will contain the points (xi, yi) in order (1xi, yi106). No two consecutive points coincide, and there are no two consecutive vertical segments or two consecutive horizontal segments.


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.


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.

Time limit 2 seconds
Memory limit 512 MiB
Input example #1
1 1
6 1
6 11
11 11
11 6
1 6
Output example #1
Input example #2
2 4
2 1
4 1
4 3
1 3
1 2
3 2
3 4
Output example #2
Input example #3
1 1
1 5
4 5
4 3
2 3
2 4
1 4
1 2
4 2
4 1
Output example #3
Source 2020 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, May 23, Problem G