Maximum Axis-Aligned Inscribed Rectangle

Eva is studying geometry, and although the current topic is convex polygons, she prefers rectangles. In her workbook, she has several drawings of convex polygons, and she wonders what the maximum area is of an axis‐aligned rectangle that can be inscribed in each of them. The sides of the rectangle must be parallel to the coordinate axes.

Given a convex polygon, determine the maximum possible area of a rectangle (with sides parallel to the coordinate axes) that can be completely contained within the polygon.

Note: The polygon is given by its vertices in either clockwise or counterclockwise order. The rectangle corners must lie inside or on the boundary of the polygon.

Hint: For a given horizontal line y, you can compute the horizontal intersection interval of the polygon and hence the available width. One approach is to discretize the possible y-coordinates and then choose the optimal pair of y-levels as the bottom and top of the rectangle.

inputFormat

The first line contains an integer n (3 ≤ n ≤ 100), the number of vertices of the convex polygon.

Each of the next n lines contains two real numbers x and y representing the coordinates of the vertex.

The vertices are given in order (either clockwise or counterclockwise).

outputFormat

Print a single floating-point number, the maximum area of an axis‐aligned rectangle that can be inscribed in the polygon. The answer is considered correct if its absolute or relative error does not exceed 10^-6.

sample

4
0 0
4 0
4 3
0 3

12.000000