F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 1185. -- [HNOI2007]最小矩形覆盖

1185: [HNOI2007]最小矩形覆盖

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 2503  Solved: 1126
[Submit][Status][Discuss]

Description

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

Input

第一行为一个整数n(3<=n<=50000)
从第2至第n+1行每行有两个浮点数,表示一个顶点的x和y坐标,不用科学计数法

Output

第一行为一个浮点数,表示所求矩形的面积(精确到小数点后5位),
接下来4行每行表示一个顶点坐标,要求第一行为y坐标最小的顶点,
其后按逆时针输出顶点坐标.如果用相同y坐标,先输出最小x坐标的顶点

Sample Input

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

Sample Output

18.00000
3.00000 0.00000
6.00000 3.00000
3.00000 6.00000
0.00000 3.00000

HINT

Source

vfleaking提供Spj

[Submit][Status][Discuss]

HOME Back