[HNOI2007] 最小矩形覆盖

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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 提供题目简述