四分之一

题目描述

ABC 250 对于以举办 ABC 1000 为目标的高桥君来说，是一个值得纪念的四分之一里程碑，因此他打算通过吃下尽可能接近他买来的披萨的 $1/4$ 来庆祝这场比赛。

高桥君买来的披萨是凸 $N$ 边形的平面形状。将披萨放在 $xy$ 平面上时，第 $i$ 个顶点的坐标为 $(X_i, Y_i)$。

高桥君决定按如下方式切割并吃掉披萨。

首先，高桥君从披萨的顶点中选择两个不相邻的顶点，用刀沿经过这两点的直线切割，将披萨分成两块。

然后，他选择其中任意一块吃掉。

设 $a$ 为高桥君买来的披萨面积的四分之一（$=1/4$），$b$ 为高桥君吃掉的披萨块的面积。求 $8 \times |a-b|$ 的最小可能值。可以证明该值一定是整数。

输入格式

输入按以下格式从标准输入给出：

N
X_1 Y_1
X_2 Y_2
…
X_N Y_N

输出格式

将答案作为整数输出。

样例

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

1

假设他沿经过第 3 个和第 5 个顶点的直线切割，并吃掉包含第 4 个顶点的块。

那么，$a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8}$，$b=4$，且 $8 \times |a-b|=1$，这是最小值。

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

1280000000000000000

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

157889

数据范围

• 输入中的所有值均为整数。
• $4 \le N \le 10^5$
• $|X_i|, |Y_i| \le 4 \times 10^8$
• 给定的点是按逆时针顺序排列的凸 $N$ 边形的顶点。