题目描述

给定一些点的坐标，求能够覆盖所有点的最小面积的矩形，输出所求矩形的面积和四个顶点坐标。

输入格式

第一行为一个整数 $n$，从第 $2$ 至第 $n+1$ 行每行有两个浮点数（精确到至多五位小数，不使用科学计数法），表示一个顶点的 $x$ 和 $y$ 坐标。

输出格式

第一行为一个浮点数，表示所求矩形的面积，接下来 $4$ 行每行表示一个顶点坐标，按逆时针输出顶点坐标。

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

提示

$3 \le n \le 50000$，坐标范围 $\in [0,10]$。保证覆盖所有点所需要的最小矩形面积至少是 $0.1$。

如果你的矩形面积为 $S'$，正确答案为 $S$，那么当 $\frac{|S'-S|}{\max\{1,S\}}<10^{-4}$，且所有点满足在矩形内或者到矩形的距离 $<10^{-4}$ 时，你的答案会被判定为正确（你可以忽略这段话，简而言之你的答案只要不是有特别大的精度误差就可以通过）。

感谢 @intruder 提供题目简述