← 返回题目列表

AtCoder · awc0103_e

E. 最大面积牧场

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

分数: 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