CF1044C.Optimal Polygon Perimeter

You are given $n$ points on the plane. The polygon formed from all the $n$ points is strictly convex, that is, the polygon is convex, and there are no three collinear points (i.e. lying in the same straight line). The points are numbered from $1$ to $n$, in clockwise order.

We define the distance between two points $p_1 = (x_1, y_1)$ and $p_2 = (x_2, y_2)$ as their Manhattan distance: $$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.$$

Furthermore, we define the perimeter of a polygon, as the sum of Manhattan distances between all adjacent pairs of points on it; if the points on the polygon are ordered as $p_1, p_2, \ldots, p_k$ $(k \geq 3)$, then the perimeter of the polygon is $d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1)$.

For some parameter $k$, let's consider all the polygons that can be formed from the given set of points, having any $k$ vertices, such that the polygon is not self-intersecting. For each such polygon, let's consider its perimeter. Over all such perimeters, we define $f(k)$ to be the maximal perimeter.

Please note, when checking whether a polygon is self-intersecting, that the edges of a polygon are still drawn as straight lines. For instance, in the following pictures:

In the middle polygon, the order of points ($p_1, p_3, p_2, p_4$) is not valid, since it is a self-intersecting polygon. The right polygon (whose edges resemble the Manhattan distance) has the same order and is not self-intersecting, but we consider edges as straight lines. The correct way to draw this polygon is ($p_1, p_2, p_3, p_4$), which is the left polygon.

Your task is to compute $f(3), f(4), \ldots, f(n)$. In other words, find the maximum possible perimeter for each possible number of points (i.e. $3$ to $n$).

给定平面上的 $n$ 个点。由全部 $n$ 个点构成的多边形是严格凸的，即该多边形为凸多边形，且不存在三点共线（即任意三点不位于同一条直线上）。这些点按顺时针顺序编号为 $1$ 至 $n$。

我们定义两点 $p_1 = (x_1, y_1)$ 与 $p_2 = (x_2, y_2)$ 之间的距离为其曼哈顿距离：

$$d(p\_1, p\_2) = |x\_1 - x\_2| + |y\_1 - y\_2|.$$

此外，我们定义一个多边形的周长为该多边形上所有相邻点对之间的曼哈顿距离之和；若多边形上的点按顺序排列为 $p_1, p_2, \ldots, p_k$（其中 $k \geq 3$），则该多边形的周长为

$$d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1).$$

对于某个参数 $k$，考虑由给定点集所能构成的所有含 $k$ 个顶点的多边形（顶点取自给定 $n$ 个点），要求该多边形不自交。对每个这样的多边形，计算其周长；在所有这些周长中，记 $f(k)$ 为最大周长。

请注意：判断一个多边形是否自交时，其各条边仍按直线段绘制。例如，在下图中：

中间的多边形，其顶点顺序为 $(p_1, p_3, p_2, p_4)$，是无效的，因为它是一个自交多边形。右侧的多边形（其边形似曼哈顿距离路径）虽具有相同顶点顺序且看似不自交，但我们仍按直线段理解边——因此它实际仍是自交的。正确的绘制方式是顺序 $(p_1, p_2, p_3, p_4)$，即左侧的多边形。

你的任务是计算 $f(3), f(4), \ldots, f(n)$，即对每个可能的顶点数（从 $3$ 到 $n$），求出对应的最大可能周长。

The first line contains a single integer $n$ ($3 \leq n \leq 3\cdot 10^5$) — the number of points.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^8 \leq x_i, y_i \leq 10^8$) — the coordinates of point $p_i$.

The set of points is guaranteed to be convex, all points are distinct, the points are ordered in clockwise order, and there will be no three collinear points.

第一行包含一个整数 $n$（$3 \leq n \leq 3\cdot 10^5$）—— 点的数量。

接下来的 $n$ 行每行包含两个整数 $x_i$ 和 $y_i$（$-10^8 \leq x_i, y_i \leq 10^8$）—— 点 $p_i$ 的坐标。

保证给定的点集是凸的，所有点互不相同，点按顺时针顺序给出，且不存在三点共线的情况。

For each $i$ ($3\leq i\leq n$), output $f(i)$.

对于每个 $i$（$3\leq i\leq n$），输出 $f(i)$。

In the first example, for $f(3)$, we consider four possible polygons:

• ($p_1, p_2, p_3$), with perimeter $12$.
• ($p_1, p_2, p_4$), with perimeter $8$.
• ($p_1, p_3, p_4$), with perimeter $12$.
• ($p_2, p_3, p_4$), with perimeter $12$.

For $f(4)$, there is only one option, taking all the given points. Its perimeter $14$.

In the second example, there is only one possible polygon. Its perimeter is $8$.

在第一个例子中，对于 $f(3)$，我们考虑四种可能的多边形：

• ($p_1, p_2, p_3$)，周长为 $12$。
• ($p_1, p_2, p_4$)，周长为 $8$。
• ($p_1, p_3, p_4$)，周长为 $12$。
• ($p_2, p_3, p_4$)，周长为 $12$。

对于 $f(4)$，只有一种选择，即取所有给定的点。其周长为 $14$。

在第二个例子中，仅存在一种可能的多边形，其周长为 $8$。