Mailing Origami

View as PDF

Submit solution

Points: 20
Time limit: 1.0s
Memory limit: 64M

Problem type

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?

Input Specification

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

Output Specification

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.

Sample Input

6
4 9
8 13
8 9
0 13
4 0
0 3

Output for Sample Input

104

David Pritchard, Troy Vasiga

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.