Minimum Area Enclosing Rectangle

Given a set of points in the plane, find a rectangle of minimum area that covers all the points. The rectangle is allowed to have an arbitrary orientation (i.e. it may be rotated) and its sides need not be parallel to the coordinate axes. Output the minimum area and the coordinates of its four vertices.

Note: The answer must be computed using high‐precision arithmetic and the final results should be printed with 6 decimal places. If there are multiple solutions, output any one of them.

inputFormat

The first line contains an integer n (n ≥ 1), the number of points. Each of the next n lines contains two floating-point numbers representing the x and y coordinates of a point.

outputFormat

On the first line, output the area of the minimum enclosing rectangle with 6 decimal places. Then output the coordinates of the four vertices of the rectangle (each vertex in one line with x and y separated by a space), also with 6 decimal places. The vertices should be listed in order (for example, starting from the bottom-left vertex and proceeding in clockwise order).

sample

4
0 0
0 1
1 1
1 0

1.000000
0.000000 0.000000
1.000000 0.000000
1.000000 1.000000
0.000000 1.000000