AT_abc250_f [ABC250F] One Fourth

题目描述

ABC250 是高桥君为举办 ABC1000 而努力的一个具有纪念意义的回合，正好是 $1/4$。
因此，高桥君买了一块披萨，打算吃掉尽可能接近 $1/4$ 的披萨来庆祝。

高桥君买的披萨是一个凸 $N$ 边形（$N \ge 4$），放在 $xy$ 平面上时，第 $i$ 个顶点的坐标为 $(X_i, Y_i)$。

高桥君打算按如下方式切披萨并食用：

• 首先，高桥君从披萨的顶点中选择两个不相邻的顶点，沿着经过这两个顶点的直线用刀切开，将披萨分成两块。
• 然后，从这两块中任选一块吃掉。

设高桥君买的披萨的面积的 $1/4$ 为 $a$，他吃掉的那块披萨的面积为 $b$，请你求出 $8 \times |a-b|$ 的最小可能值。可以证明，这个值总是整数。

输入格式

输入以如下格式从标准输入读入：

$N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\dots$ $X_N$ $Y_N$

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1

输入输出样例 #2

输入 #2

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

输出 #2

1280000000000000000

输入输出样例 #3

输入 #3

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

输出 #3

157889

说明/提示

限制条件

• 所有输入均为整数。
• $4 \le N \le 10^5$
• $|X_i|, |Y_i| \le 4 \times 10^8$
• 输入的顶点按逆时针顺序给出，且构成一个凸 $N$ 边形。

样例解释 1

假设沿着第 $3$ 个顶点和第 $5$ 个顶点连线切开披萨，并吃掉包含第 $4$ 个顶点的那一块。此时，$a = \frac{33}{2} \times \frac{1}{4} = \frac{33}{8}$，$b = 4$，$8 \times |a-b| = 1$，这是可能的最小值。

由 ChatGPT 4.1 翻译