2142

2142. 最小矩形覆盖

题目

已知平面上 不共线 的一组点的坐标，求覆盖这组点的面积最小的矩形。

输出矩形的面积和四个顶点的坐标。

输入格式

第一行包含一个整数 $n$，表示点的数量。

接下来 $n$ 行，每行包含两个用空格隔开的浮点数，表示一个点的 $x$ 坐标和 $y$ 坐标。

不用科学计数法，但如果小数部分为 $0$，则可以写成整数。

输出格式

共 $5$ 行，第 $1$ 行输出一个浮点数，表示所求得的覆盖输入点集的最小矩形的面积。

接下来 $4$ 行，每行包含两个用空格隔开的浮点数，表示所求矩形的一个顶点的 $x$ 坐标和 $y$ 坐标。

先输出 $y$ 坐标最小的顶点的 $x,y$ 坐标，如果有两个点的 $y$ 坐标同时达到最小，则先输出 $x$ 坐标较小者的 $x,y$ 坐标。

然后，按照逆时针的顺序输出其他三个顶点的坐标。

不用科学计数法，精确到小数点后 $5$ 位，后面的 $0$ 不可省略。

答案不唯一，输出任意一组正确结果即可。

数据范围

$3 \le n \le 50000$

输入样例：

6
1.0 3.00000
1 4.00000
2.00000 1
3 0.00000
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

题解