Mailing Origami

Time limit1sMemory limit256 MB

Summary

Find the area of the smallest rotated rectangle enclosing N given points, rounded to the nearest integer.

Level: Medium7 of 10
Topics: Geometry, Sorting, Two pointers
Solved: No attempts yet

Problem

You want to mail a piece of origami you folded to your mom.

The postage depends on the area of the envelope: the smaller the envelope, the cheaper the shipment. You cannot fold the origami again to make it smaller, and the envelope has to be rectangular. The envelope may be turned to any angle, so its sides do not have to be parallel to the coordinate axes.

The outline of the origami is given as $N$ vertices listed in order along its boundary, and the boundary may fold back over itself. Find the area of the smallest rectangular envelope that contains the origami.

Input

The first line contains the integer $N$ , the number of vertices of the origami ( $3 \le N \le 100000$ ).

Each of the next $N$ lines contains two integers $x$ and $y$ , the coordinates of one vertex ( $0 \le x \le 10^7$ , $0 \le y \le 10^7$ ). All vertices are distinct, and no single line contains all of them.

Output

Print the area of the smallest envelope that contains the origami, rounded to the nearest integer. No input has a smallest envelope whose area has a fractional part between 0.49 and 0.51.

Examples2

Example 1
Input
```
6
4 9
8 13
8 9
0 13
4 0
0 3
```
Expected output
```
104
```
Example 2
Input
```
5
0 0
6 0
6 4
0 4
3 2
```
Expected output
```
24
```