147. Triangulation Rocks the Nation Again

Codeforces

IDCF10269147

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

_This is a sigificantly harder version of a previous problem in the contest. We recommend you solve the earlier problem first._ You're given the coordinates of an $n$-sided polygon. The polygon is not necessarily a regular polygon (the sides and angles are not necessarily equal), but the polygon is guaranteed to be convex (the polygon will not contain any angles greater than or equal to 180 degrees). Given this information, figure out the area of the given polygon. The first line of input consists of a positive integer $n$ greater than three: the number of sides of the polygon. The next $n$ lines each contain two space-separated integers: the $x$ and $y$ coordinates of each point of the polygon. None of the sides of the polygon will be completely vertical. Output a single decimal number $a$: the area of the given $n$-sided polygon. Remember, the polygon is guaranteed to be a convex polygon. It might help to use your code from the easier version ## Input The first line of input consists of a positive integer $n$ greater than three: the number of sides of the polygon. The next $n$ lines each contain two space-separated integers: the $x$ and $y$ coordinates of each point of the polygon.None of the sides of the polygon will be completely vertical. ## Output Output a single decimal number $a$: the area of the given $n$-sided polygon. Remember, the polygon is guaranteed to be a convex polygon. [samples] ## Note It might help to use your code from the easier version

**Definitions** Let $ n \in \mathbb{Z} $, $ n \geq 4 $, be the number of vertices of a convex polygon. Let $ P = ( (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) ) $ be the ordered sequence of vertex coordinates in counterclockwise or clockwise traversal. **Constraints** 1. $ n \geq 4 $ 2. The polygon is convex. 3. No side is vertical. 4. Coordinates are integers: $ x_i, y_i \in \mathbb{Z} $ for all $ i \in \{1, \dots, n\} $. **Objective** Compute the area $ A $ of the polygon using the shoelace formula: $$ A = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right| $$ where $ (x_{n+1}, y_{n+1}) = (x_1, y_1) $.

API Response (JSON)

{
  "problem": {
    "name": "147. Triangulation Rocks the Nation Again",
    "description": {
      "content": "_This is a sigificantly harder version of a previous problem in the contest. We recommend you solve the earlier problem first._ You're given the coordinates of an $n$-sided polygon. The polygon is no",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269147"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_This is a sigificantly harder version of a previous problem in the contest. We recommend you solve the earlier problem first._\n\nYou're given the coordinates of an $n$-sided polygon. The polygon is no...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 4 $, be the number of vertices of a convex polygon.  \nLet $ P = ( (x_1, y_1), (x_2, y_2), \\dots, (x_n, y_n) ) $ be the ordered sequence of vertex c...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments