← 返回题目列表

AtCoder · abc250_f

I. 四分之一

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

ABC 250 对于高桥来说是一个值得纪念的季度里程碑,他的目标是持有 ABC 1000, 所以他打算通过吃尽可能近的食物来庆祝这场比赛 1/4 他买了尽可能多的披萨。

高桥买的披萨平面形状为凸面 N-gon。 当披萨放在 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-gon 按逆时针顺序排列。

输入

输入由标准输入按以下格式给出:

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-rd 和 5-th 顶点并吃掉包含 4- 第一个顶点。
然后, a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8}, b=4,和 8 \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