{"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 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).\n\nGiven this information, figure out the area of the given polygon.\n\nThe first line of input consists of a positive integer $n$ greater than three: the number of sides of the polygon. \n\nThe next $n$ lines each contain two space-separated integers: the $x$ and $y$ coordinates of each point of the polygon.\n\nNone of the sides of the polygon will be completely vertical.\n\nOutput a single decimal number $a$: the area of the given $n$-sided polygon. Remember, the polygon is guaranteed to be a convex polygon.\n\nIt might help to use your code from the easier version\n\n## Input\n\nThe 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.\n\n## Output\n\nOutput a single decimal number $a$: the area of the given $n$-sided polygon. Remember, the polygon is guaranteed to be a convex polygon.\n\n[samples]\n\n## Note\n\nIt might help to use your code from the easier version","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 coordinates in counterclockwise or clockwise traversal.\n\n**Constraints**  \n1. $ n \\geq 4 $  \n2. The polygon is convex.  \n3. No side is vertical.  \n4. Coordinates are integers: $ x_i, y_i \\in \\mathbb{Z} $ for all $ i \\in \\{1, \\dots, n\\} $.\n\n**Objective**  \nCompute the area $ A $ of the polygon using the shoelace formula:  \n$$\nA = \\frac{1}{2} \\left| \\sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \\right|\n$$  \nwhere $ (x_{n+1}, y_{n+1}) = (x_1, y_1) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269147","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}