Easy Geometry

Time limit1sMemory limit128 MB

Summary

Find the largest area of an axis-aligned rectangle that fits inside a given convex polygon.

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

Problem

Eva studies geometry. The current topic is convex polygons, but Eva prefers rectangles. Her workbook has several convex polygons drawn in it, and she wants to know the area of the largest rectangle that fits inside each of them.

Help Eva. Given a convex polygon, find the largest possible area of a rectangle that fits inside it. The sides of the rectangle must be parallel to the coordinate axes.

Input

The first line contains a single integer $n$ , the number of sides of the polygon ( $3 \le n \le 100\,000$ ). Each of the following $n$ lines contains the Cartesian coordinates of one vertex of the polygon, two integers $x_i$ and $y_i$ ( $-10^9 \le x_i, y_i \le 10^9$ ). The vertices are given in clockwise order.

The polygon is convex.

Output

Print one line with the largest area of a rectangle that fits inside the polygon and has its sides parallel to the coordinate axes, rounded to six digits after the decimal point. Always print all six digits.

No answer in the input data lies on a rounding boundary.

Examples2

Example 1
Input
```
4
5 1
2 4
3 7
7 3
```
Expected output
```
4.000000
```
Example 2
Input
```
5
1 1
1 4
4 7
7 4
7 1
```
Expected output
```
18.000000
```