{"problem":{"name":"H. Split Game","description":{"content":"Consider the following game about splitting a simple polygon with N vertices on a plane. The purpose of this game is using a straight line which passes through the origin to split the given simple pol","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10123H"},"statements":[{"statement_type":"Markdown","content":"Consider the following game about splitting a simple polygon with N vertices on a plane. The purpose of this game is using a straight line which passes through the origin to split the given simple polygon into as many non-zero area regions as possible. Please finish the game with the best result possible.\n\nThe input consists of N + 1 lines. The first line contains an integer N. The i-th of the following N lines consists of two integers xi and yi indicating the vertices of the given polygon in counter-clockwise order. Also, the actual lower bound on N is 3.\n\nOutput one integer: the maximum number of non-zero area regions into which the given polygon can be split by a single line passing through the origin.\n\n## Input\n\nThe input consists of N + 1 lines. The first line contains an integer N. The i-th of the following N lines consists of two integers xi and yi indicating the vertices of the given polygon in counter-clockwise order. Also, the actual lower bound on N is 3.  1 ≤ N ≤ 105  1 ≤ xi, yi ≤ 109  if i ≠ j, then (xi, yi) ≠ (xj, yj)  the vertices are given in counter-clockwise order  the polygon is simple: its sides have no common points except the vertices \n\n## Output\n\nOutput one integer: the maximum number of non-zero area regions into which the given polygon can be split by a single line passing through the origin.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ N \\geq 3 $, be the number of vertices of a simple polygon.  \nLet $ P = (v_1, v_2, \\dots, v_N) $, where $ v_i = (x_i, y_i) \\in \\mathbb{R}^2 $, be the sequence of vertices given in counter-clockwise order.  \n\nLet $ \\mathcal{L} $ be the set of all lines in $ \\mathbb{R}^2 $ passing through the origin $ (0,0) $.  \n\n**Constraints**  \n- The polygon $ P $ is simple (non-self-intersecting).  \n- The origin $ (0,0) $ may lie inside, on the boundary, or outside the polygon.  \n\n**Objective**  \nFind the maximum number of connected components of positive area into which $ P $ can be partitioned by a single line $ \\ell \\in \\mathcal{L} $.  \n\nThat is, compute:  \n$$\n\\max_{\\ell \\in \\mathcal{L}} \\left| \\left\\{ C \\subseteq P \\cap \\mathbb{R}^2 \\mid C \\text{ is a connected component of } P \\setminus \\ell \\text{ and } \\text{area}(C) > 0 \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10123H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}