Rectangles
A polygon is provided on a plane. Your task is to write a program, RECT, that finds the rectangle with the smallest possible area that can completely enclose the given polygon. For instance, consider the polygon shown below:
The corresponding minimal rectangle would be:
Input
The input begins with an integer N on the 1st line, representing the number of vertices of the polygon (3 ≤ N ≤ 3000). The following N lines each contain two real numbers, X_{i} and Y_{i}, which are the coordinates of the polygon's vertices listed in clockwise order.
All coordinates in both the input and output files are real numbers formatted for standard input-output functions.
The recommended data type for coordinates is Real in Pascal and float in C and C++.
Output
The output should consist of 5 lines: the first line should contain the number S, which is the area of the rectangle. The next 4 lines should each contain a pair of coordinates, X_{i} Y_{i}, representing the vertices of the rectangle in any order of traversal.
The calculated area and the coordinates of the rectangle must be accurate to within 10^{-5}.