102505: [AtCoder]ABC250 F - One Fourth

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

问题描述

ABC 250对目标是举办ABC 1000的Takahashi来说是一个值得纪念的四分之一里程碑，所以他打算通过尽可能接近吃掉他买的一块披萨的四分之一来庆祝这场比赛。

Takahashi买的披萨有一个凸的N边形平面形状。当披萨放在一个xy平面上时，第i个顶点的坐标为(Xi，Yi)。

Takahashi决定按照以下方式切割并吃掉披萨。

• 首先，Takahashi从披萨的顶点中选择两个不相邻的顶点，并沿着通过这两个点的线用刀切开披萨，将披萨分成两块。
• 然后，他选择一块自己喜欢的披萨吃掉。

设a为Takahashi买的披萨的四分之一（=1/4）的面积，b为Takahashi吃的披萨的面积。找出8×|a-b|的最小可能值。我们可以证明这个值总是整数。

约束条件

• 输入中的所有值都是整数。
• 4≤N≤10^5
• |Xi|, |Yi|≤4×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=33/2×1/4=33/8，b=4，8×|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