F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister 捐赠本站
Notice:开心刷题:)
Problem 2146. -- Construct -- 衡阳八中OJ离线版-2014-11-04

2146: Construct

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 52  Solved: 25
[Submit][Status]

Description

随着改革开放的深入推进…… 小T家要拆迁了…… 当对未来生活充满美好憧憬的小T看到拆迁协议书的时候,小T从一位大好的社会主义青年变成了绝望的钉子户。 由于小T的家位于市中心,拆迁工作又难以进行,有关部门决定先把小T家用围栏围起来,以免影响市容。考虑到要建设资源节约型社会,他们希望所用的围栏长度越短越好,由于市中心寸土寸金,在围栏长度最短的情况下,围出的多边形面积越小越好。 为了简化问题,我们约定,小T的家是一个多边形,并且每条边与坐标轴平行,围栏构成的也是多边形,每条边与坐标轴平行。

Input

在第一行列出整数n——多边形的顶点的数量。在以下n行中的每一行都有两个整数——沿逆时针方向走过这个多边形顺次所经过的顶点的坐标。边界的任意三个连续顶点不在一条直线上。多边形的边界不含自交和自切。

Output

输出两行,第一行为围栏最短的长度,第二行为长度最短的前提下,最小的面积。

Sample Input

8
0 0
9 0
9 9
6 9
6 3
3 3
3 6
0 6

Sample Output

36
63

【数据范围】
对于100%的数据4≤n≤100000,坐标的绝对值不超过109 。

HINT

Source

[Submit][Status]

HOME Back