Contest Duration: - (local time) (100 minutes) Back to Home
F - One Fourth /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

ABC250 は、 ABC1000 の開催を目指す高橋くんにとってちょうど 1/4 となる記念すべき回です。
そこで、高橋くんはピザを 1 枚買ってきて、そのピザのうちなるべく 1/4 に近い分量を食べて祝うことにしました。

• まず、高橋くんはピザの頂点のうち隣接しない 2 頂点を選び、それらを通る直線に沿ってナイフを入れ、ピザを 2 つに切り分ける。
• その後、 2 つのピースのうち好きなものをどちらか 1 つ選んで食べる。

### 制約

• 入力は全て整数
• 4 \le N \le 10^5
• |X_i|, |Y_i| \le 4 \times 10^8
• 入力される頂点は反時計回りに凸 N 角形をなす。

### 入力

N
X_1 Y_1
X_2 Y_2
\dots
X_N Y_N


### 入力例 1

5
3 0
2 3
-1 3
-3 1
-1 -1


### 出力例 1

1


3 番目の頂点と 5 番目の頂点を通る直線に沿ってピザを切り分け、 4 番目の頂点を含む側のピースを食べたとします。
このとき、a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8}b=48 \times |a-b|=1 であり、これがありえる最小値です。

### 入力例 2

4
400000000 400000000
-400000000 400000000
-400000000 -400000000
400000000 -400000000


### 出力例 2

1280000000000000000


### 入力例 3

6
-816 222
-801 -757
-165 -411
733 131
835 711
-374 979


### 出力例 3

157889


Score : 500 points

### Problem Statement

ABC 250 is a commemorable quarter milestone for Takahashi, who aims to hold ABC 1000, so he is going to celebrate this contest by eating as close to 1/4 of a pizza he bought as possible.

The pizza that Takahashi bought has a planar shape of convex N-gon. When the pizza is placed on an xy-plane, the i-th vertex has coordinates (X_i, Y_i).

Takahashi has decided to cut and eat the pizza as follows.

• First, Takahashi chooses two non-adjacent vertices from the vertices of the pizza and makes a cut with a knife along the line passing through those two points, dividing the pizza into two pieces.
• Then, he chooses one of the pieces at his choice and eats it.

Let a be the quarter (=1/4) of the area of the pizza that Takahashi bought, and b be the area of the piece of pizza that Takahashi eats. Find the minimum possible value of 8 \times |a-b|. We can prove that this value is always an integer.

### Constraints

• All values in input are integers.
• 4 \le N \le 10^5
• |X_i|, |Y_i| \le 4 \times 10^8
• The given points are the vertices of a convex N-gon in the counterclockwise order.

### Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\dots
X_N Y_N


### Output

Print the answer as an integer.

### Sample Input 1

5
3 0
2 3
-1 3
-3 1
-1 -1


### Sample Output 1

1


Suppose that he makes a cut along the line passing through the 3-rd and the 5-th vertex and eats the piece containing the 4-th vertex.
Then, a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8}, b=4, and 8 \times |a-b|=1, which is minimum possible.

### Sample Input 2

4
400000000 400000000
-400000000 400000000
-400000000 -400000000
400000000 -400000000


### Sample Output 2

1280000000000000000


### Sample Input 3

6
-816 222
-801 -757
-165 -411
733 131
835 711
-374 979


### Sample Output 3

157889