E - 最大面積の牧場 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は広大な平原に牧場を作ろうとしています。平原には目印となる N 本の杭が打たれており、これらの杭の中から 3 本以上を選んでフェンスの支柱とし、選んだ杭を頂点とする凸多角形の牧場を作りたいと考えています。

牧場をできるだけ広くするために、高橋君はフェンスで囲まれた面積が最大となるような杭の選び方を知りたいです。

具体的には、二次元平面上に N 本の杭が (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) の位置に打たれています。これらの杭の中から 3 本以上を選び、選んだ杭の集合をちょうど頂点の集合とする 狭義の凸多角形 を作ります。ここで、狭義の凸多角形とは、すべての内角が 180 度未満である凸多角形を指します。すなわち、選んだ杭はすべて凸多角形の頂点であり、かつ凸多角形の頂点はすべて選んだ杭でなければなりません。

このような選び方すべてのうち、凸多角形の面積の最大値を求めてください。

以下のような選び方は条件を満たさないことに注意してください。

  • 選んだ杭の中に、凸多角形の辺上（頂点を除く）に位置するものがある場合。このとき、その杭における内角は 180 度となり、狭義の凸多角形の条件に反します。
  • 選んだ杭がすべて一直線上にある場合。この場合、凸多角形を構成できません。

条件を満たす杭の選び方が少なくとも 1 つ存在することは保証されます（一直線上にない 3 本の杭が存在すれば、それらを頂点とする三角形は狭義の凸多角形です）。

座標がすべて整数であるとき、面積の 2 倍の値は必ず整数になることが知られています。面積の最大値を 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
  • 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

1 行目には、杭の本数を表す整数 N が与えられる。続く N 行の i 行目には、i 番目の杭の x 座標 X_i と y 座標 Y_i が空白区切りで与えられる。

出力

条件を満たす凸多角形の面積の最大値を S としたとき、2S を整数として 1 行で出力せよ。

入力例 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

Score : 466 pts

Problem Statement

Takahashi is trying to build a pasture on a vast plain. There are N stakes driven into the plain as landmarks. He wants to select 3 or more of these stakes to use as fence posts, forming a pasture in the shape of a convex polygon whose vertices are the selected stakes.

To make the pasture as large as possible, Takahashi wants to know the selection of stakes that maximizes the area enclosed by the fence.

Specifically, N stakes are placed at positions (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) on a two-dimensional plane. Select 3 or more of these stakes to form a strictly convex polygon whose set of vertices is exactly the set of selected stakes. Here, a strictly convex polygon refers to a convex polygon in which all interior angles are less than 180 degrees. That is, all selected stakes must be vertices of the convex polygon, and all vertices of the convex polygon must be selected stakes.

Among all such valid selections, find the maximum area of the convex polygon.

Note that the following selections do not satisfy the conditions:

  • If any selected stake lies on an edge of the convex polygon (excluding the vertices). In this case, the interior angle at that stake is 180 degrees, violating the strictly convex polygon condition.
  • If all selected stakes are collinear. In this case, no convex polygon can be formed.

It is guaranteed that at least one valid selection of stakes exists (if there exist 3 stakes that are not collinear, the triangle with those stakes as vertices is a strictly convex polygon).

It is known that when all coordinates are integers, twice the area is always an integer. Let S be the maximum area. Output 2S as an integer.

Constraints

  • 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, then (X_i, Y_i) \neq (X_j, Y_j) (all stakes are at distinct positions)
  • Not all stakes are collinear
  • All input values are integers

Input

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

The first line contains an integer N representing the number of stakes. The i-th of the following N lines contains the x-coordinate X_i and y-coordinate Y_i of the i-th stake, separated by a space.

Output

Let S be the maximum area of a convex polygon satisfying the conditions. Output 2S as an integer on a single line.

Sample Input 1

5
0 0
4 0
4 3
0 3
2 1

Sample Output 1

24

Sample Input 2

6
0 0
2 0
4 0
4 2
0 2
1 1

Sample Output 2

16

Sample Input 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

Sample Output 3

137

Sample Input 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

Sample Output 4

6590000

Sample Input 5

3
-1000000000 -1000000000
1000000000 -1000000000
-1000000000 1000000000

Sample Output 5

4000000000000000000