{"raw_statement":[{"iden":"statement","content":"You are given a strictly convex polygon. Find the minimal possible area of non-degenerate triangle whose vertices are the vertices of the polygon.\n\nThe first line contains a single integer n (3 ≤ n ≤ 200000) — the number of polygon vertices.\n\nEach of the next n lines contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of polygon vertices.\n\nThe polygon is guaranteed to be strictly convex. Vertices are given in the counterclockwise order.\n\nIt is known that the area of triangle whose vertices are the integer points on the grid is either integer or half-integer.\n\nOutput a single integer — the required area, *multiplied by 2*.\n\nIt is recommended to make all calculations using integer numbers, because floating point precision most likely would not be enough.\n\n"},{"iden":"input","content":"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 xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of polygon vertices.The polygon is guaranteed to be strictly convex. Vertices are given in the counterclockwise order."},{"iden":"output","content":"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*."},{"iden":"examples","content":"Input40 13 03 3-1 3Output5Input30 01 00 1Output1Input4-999999991 999999992-999999993 -999999994999999995 -999999996999999997 999999998Output3999999948000000156"},{"iden":"note","content":"It is recommended to make all calculations using integer numbers, because floating point precision most likely would not be enough."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 200000 $ be the number of vertices.  \nLet $ P = (v_0, v_1, \\dots, v_{n-1}) $ be the sequence of vertices of a strictly convex polygon in counterclockwise order, where $ v_i = (x_i, y_i) \\in \\mathbb{Z}^2 $.\n\n**Constraints**  \n1. The polygon is strictly convex.  \n2. Vertices are given in counterclockwise order.  \n3. $ -10^9 \\leq x_i, y_i \\leq 10^9 $ for all $ i $.\n\n**Objective**  \nFind the minimum value of $ 2 \\cdot \\text{Area}(\\triangle v_i v_j v_k) $ over all triples $ (i, j, k) $ with $ 0 \\leq i < j < k < n $, where the area of triangle $ \\triangle v_i v_j v_k $ is computed via the cross product formula:  \n$$\n\\text{Area}(\\triangle v_i v_j v_k) = \\frac{1}{2} \\left| (x_j - x_i)(y_k - y_i) - (x_k - x_i)(y_j - y_i) \\right|\n$$  \nThus, the objective is to compute:  \n$$\n\\min_{0 \\leq i < j < k < n} \\left| (x_j - x_i)(y_k - y_i) - (x_k - x_i)(y_j - y_i) \\right|\n$$  \nand output this integer value.","simple_statement":"Given a strictly convex polygon with n vertices in counter-clockwise order, find the smallest possible area (multiplied by 2) of any non-degenerate triangle formed by three of its vertices.","has_page_source":false}