405049: GYM101755 B Minimal Area

You are given a strictly convex polygon. Find the minimal possible area of non-degenerate triangle whose vertices are the vertices of the polygon.

The first line contains a single integer n (3 ≤ n ≤ 200000) — the number of polygon vertices.

Each of the next n lines contains two integers x_i and y_i ( - 10⁹ ≤ x_i, y_i ≤ 10⁹) — the coordinates of polygon vertices.

The polygon is guaranteed to be strictly convex. Vertices are given in the counterclockwise order.

It is known that the area of triangle whose vertices are the integer points on the grid is either integer or half-integer.

Output a single integer — the required area, multiplied by 2.

4
0 1
3 0
3 3
-1 3

5

3
0 0
1 0
0 1

1

4
-999999991 999999992
-999999993 -999999994
999999995 -999999996
999999997 999999998

3999999948000000156

It is recommended to make all calculations using integer numbers, because floating point precision most likely would not be enough.