CF1044C Optimal Polygon Perimeter

给定平面上的 $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$ 个顶点组成的所有多边形，要求多边形**不自交**。对于每个这样的多边形，计算其周长。在所有这些周长中，定义 $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$），求出最大可能的周长。

第一行包含一个整数 $n$（$3 \leq n \leq 3\cdot 10^5$）——点的数量。 接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$-10^8 \leq x_i, y_i \leq 10^8$）——第 $i$ 个点 $p_i$ 的坐标。 保证所有点构成一个凸包，所有点互不相同，点按顺时针顺序排列，且不存在三点共线。

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

在第一个样例中，对于 $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$。 由 ChatGPT 4.1 翻译