Description

Given the coordinates of several points, find the rectangle with the minimum area that covers all the points. Output the area of the rectangle and the coordinates of its four vertices.

Input Format

The first line contains an integer $n$. From line $2$ to line $n+1$, each line contains two floating-point numbers (with up to five decimal places, not in scientific notation), representing the $x$ and $y$ coordinates of a point.

Output Format

The first line contains a floating-point number, which is the area of the rectangle. The next $4$ lines each contain the coordinates of a vertex, output in counterclockwise order.

6
1.0 3.00000
1 4.00000
2.0000 1
3 0.0000
3.00000 6
6.0 3.0

18.00000
3.00000 0.00000
6.00000 3.00000
3.00000 6.00000
0.00000 3.00000

Hint

$3 \le n \le 50000$, coordinate range $\in [0, 10]$. It is guaranteed that the minimum rectangle area needed to cover all points is at least $0.1$.

If your rectangle area is $S'$, and the correct answer is $S$, then your answer will be judged correct when $\frac{|S' - S|}{\max\{1, S\}} < 10^{-4}$, and all points are inside the rectangle or have distance $< 10^{-4}$ to the rectangle (you can ignore this paragraph; in short, your answer will pass as long as the numerical error is not particularly large).

Thanks to @intruder for providing the problem summary.

Translated by ChatGPT 5