分数: 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