分数: 466 分
问题陈述
高桥正试图在广阔的平原上建造牧场。有 N 木桩被打入平原作为地标。他想选择 3 或更多这些木桩用作栅栏柱,形成凸多边形形状的牧场,其顶点是选定的木桩。
为了使牧场尽可能大,高桥想知道如何选择木桩,以最大化围栏所包围的面积。
具体来说, N 木桩放置在位置 (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) 在二维平面上。选择 3 或更多这些股份形成 严格凸多边形 其顶点集正是所选桩的集。这里,严格凸多边形是指所有内角都小于的凸多边形 180 度。即,所有选定的桩必须是凸多边形的顶点,并且凸多边形的所有顶点必须是选定的桩。
在所有此类有效选择中,找到凸多边形的最大面积。
请注意,以下选择不满足条件:
- 如果任何选定的桩位于凸多边形的边上(不包括顶点)。在这种情况下,该桩的内角是 180 度,违反严格凸多边形条件。
- 如果所有选定的桩共线。在这种情况下,不能形成凸多边形。
保证至少存在一种有效的赌注选择(如果存在 3 不共线的桩,以这些桩为顶点的三角形是严格凸多边形)。
众所周知,当所有坐标都是整数时,面积的两倍始终是整数。让 S 是最大面积。输出 2S 作为整数。
约束
- 3 \leq N \leq 2 \times 10^5
- -10^9 \leq X_i \leq 10^9
- -10^9 \leq Y_i \leq 10^9
- If i \neq j,那么 (X_i, Y_i) \neq (X_j, Y_j) (所有赌注都位于不同的位置)
- 并非所有木桩都是共线的
- 所有输入值均为整数
输入
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
第一行包含一个整数 N 代表股份数量。的 i- 以下各项 N 行包含 x- 坐标 X_i 和 y- 坐标 Y_i 的 i第一个桩,以空格分隔。
输出
让 S 是满足条件的凸多边形的最大面积。输出 2S 作为单行上的整数。
示例输入 1
5 0 0 4 0 4 3 0 3 2 1
示例输出 1
24
示例输入 2
6 0 0 2 0 4 0 4 2 0 2 1 1
示例输出 2
16
示例输入 3
15 -5 0 -3 -4 0 -5 4 -3 5 1 2 5 -2 4 -4 2 0 0 1 1 -1 1 2 -1 -2 -1 0 3 3 0
示例输出 3
137
示例输入 4
40 -1000 -200 -900 -600 -500 -900 0 -1000 450 -850 850 -500 1100 0 950 550 600 900 100 1050 -400 950 -800 650 -1100 100 -700 -100 -600 200 -300 -300 -200 100 0 0 100 -400 250 200 300 600 500 -100 700 300 -100 700 -500 500 -950 0 1000 100 50 -750 -50 850 650 -650 -650 -650 400 400 -400 -450 750 -250 -750 350 200 -200 -200 -600 550 700 -1000 -50 900 -450
示例输出 4
6590000
示例输入 5
3 -1000000000 -1000000000 1000000000 -1000000000 -1000000000 1000000000
示例输出 5
4000000000000000000