B. Minimal Area

Codeforces

IDCF10175B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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 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. 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*. It is recommended to make all calculations using integer numbers, because floating point precision most likely would not be enough. ## Input 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. ## Output 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*. [samples] ## Note It is recommended to make all calculations using integer numbers, because floating point precision most likely would not be enough.

**Definitions** Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 200000 $ be the number of vertices. Let $ 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 $. **Constraints** 1. The polygon is strictly convex. 2. Vertices are given in counterclockwise order. 3. $ -10^9 \leq x_i, y_i \leq 10^9 $ for all $ i $. **Objective** Find 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: $$ \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| $$ Thus, the objective is to compute: $$ \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| $$ and output this integer value.

API Response (JSON)

{
  "problem": {
    "name": "B. Minimal Area",
    "description": {
      "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. The first line contains a single integer n (3 ≤ n ≤ ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10175B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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 ≤ ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments