P3187 [HNOI2007] 最小矩形覆盖
题目描述
给定一些点的坐标,求能够覆盖所有点的最小面积的矩形,输出所求矩形的面积和四个顶点坐标。
输入格式
第一行为一个整数 $n$,从第 $2$ 至第 $n+1$ 行每行有两个浮点数(精确到至多五位小数,不使用科学计数法),表示一个顶点的 $x$ 和 $y$ 坐标。
输出格式
第一行为一个浮点数,表示所求矩形的面积,接下来 $4$ 行每行表示一个顶点坐标,**按逆时针**输出顶点坐标。
说明/提示
$3 \le n \le 50000$,坐标范围 $\in [0,10]$。保证覆盖所有点所需要的最小矩形面积至少是 $0.1$。
如果你的矩形面积为 $S'$,正确答案为 $S$,那么当 $\frac{|S'-S|}{\max\{1,S\}}