You would like to mail some origami you have made to your mom.

The price of mailing is dependent on the area of the envelope used to mail it: the smaller the envelope area, the less cost to ship. You cannot fold the origami shape to make it smaller. Of course, the envelope you are shipping the origami in must be rectangular.

Consider the vertices which represent the points along the boundary of the paper in order, such that the edge of the paper may fold over itself. Given the vertices describing the origami shape, what is the area of the smallest envelope that you can use to mail the origami?


The first line contains the integer N (3 ≤ N ≤ 100000) which is the number of vertices describing your origami. The next N lines contain two integers, x y, the x-coordinate and ycoordinate of that particular vertex 0 ≤ x ≤ 107; 0 ≤ y ≤ 107. You should assume all vertices are distinct, and that there is no line which contains all vertices.


Output the area of the smallest envelope that will contain the origami, rounded to the nearest integer. You can assume that no test case will have the area of the smallest envelope containing the given vertices have a fractional part between 0.49 and 0.51.

Example input
4 9
8 13
8 9
0 13
4 0
0 3
Example output
Time and memory limit:

  • 2 seconds
  • 256MB

Problem source: DMOJ

David Pritchard, Troy Vasiga
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.