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

Data Range

对于 100% 的数据, 满足:\(4 \leq n \leq 10^5, 0 \leq |x_i|, |y_i| \leq 10^9\).

Explanation

我们先把多边形去掉, 因为反正也用不到......

然后整个问题就变成了一个在点集上操作的问题. 这道题要求的是这个点集的曼哈顿凸包, 那么周长就是 \(x\) 轴最大值最小值差和 \(y\) 轴最大值最小值的差的和的两倍. 那么面积 还是比较好求的, 然后直接用一个单调栈就可以了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

#define maximize(__x,__y) __x=max(__x,__y)
#define minimize(__x,__y) __x=min(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 100100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

struct point {
    lli x, y;
} pnt[maxn];
bool operator < (point a, point b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y; }

int n;
point* stk[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &pnt[i].x, &pnt[i].y);
    // Calculating circumference
    lli xmx = -infinit, xmn = infinit,
        ymx = -infinit, ymn = infinit;
    for (int i = 1; i <= n; i++) {
        maximize(xmx, pnt[i].x);
        minimize(xmn, pnt[i].x);
        maximize(ymx, pnt[i].y);
        minimize(ymn, pnt[i].y);
    }
    lli res_1 = (xmx - xmn) * 2 + (ymx - ymn) * 2;
    // Calculating area with (manhattan) convex hull
    sort(pnt + 1, pnt + n + 1);
    int i = 1;
    // Initial stack building
    int top = 0;
    lli area = 0;
    for (i = 1; i <= n; i++) {
        if (!top || pnt[i].y >= stk[top]->y)
            stk[++top] = &pnt[i];
        if (pnt[i].y == ymx)
            break;
    }
    for (i += 1; i <= n; i++) {
        while (pnt[i].y > stk[top]->y)
            top -= 1;
        stk[++top] = &pnt[i];
    }
    for (int i = 2; i <= top; i++)
        area += min(stk[i-1]->y, stk[i]->y) * (stk[i]->x - stk[i-1]->x);
    // Doo it on the other side
    top = 0;
    for (i = 1; i <= n; i++) {
        if (!top || pnt[i].y <= stk[top]->y)
            stk[++top] = &pnt[i];
        if (pnt[i].y == ymn)
            break;
    }
    for (i += 1; i <= n; i++) {
        while (pnt[i].y < stk[top]->y)
            top -= 1;
        stk[++top] = &pnt[i];
    }
    for (int i = 2; i <= top; i++)
        area -= max(stk[i-1]->y, stk[i]->y) * (stk[i]->x - stk[i-1]->x);
    lli res_2 = area;
    // Print results
    printf("%lld\n%lld\n", res_1, res_2);
    return 0;
}