F - 四分之一

得分：500点

问题描述

对于目标要达到的ABC 1000这一重要节点，高护研决定庆祝一下，他决定吃掉刚买的一块比尽量向$\frac{1}{4}$接近的披萨。

他买的披萨是一个凸N边形。 当披萨放在xy平面上，第i个顶点的坐标为$(X_i, Y_i)$。

高护研决定以下面的方式分割并吃掉披萨。

• 首先，高护研从披萨的顶点中选择两个不相邻的点，并且使用刀沿着通过这两点的直线将披萨分割成两部分。
• 接下来，他可根据自己的选择吃掉其中的一部分。

称$a$是高护研购买的披萨的四分之一（$=1/4$）面积，$b$是高护研吃掉的那块披萨的面积。 找出$8 \times |a-b|$的最小可能值。 证明这个值总是一个整数。

约束

• 所有输入的值都是整数。
• $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$

输出

将答案作为一个整数输出。

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