← 返回题目列表

Codeforces · 1044/C

C. 最佳多边形周长

中文机器翻译题面 查看原题

您在飞机上获得 $$$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$$$) — 点 $$$p_i$$$ 的坐标。

点集保证是凸的,所有点都是不同的,点按顺时针顺序排列,并且不会有三个共线的点。

输出

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

示例

输入 #1

4
2 4
4 3
3 0
1 3

输出 #1

12 14

输入 #2

3
0 0
0 2
2 0

输出 #2

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$$$。