{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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 "},{"iden":"output","content":"Output 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."},{"iden":"examples","content":"Input41 12 12 21 2Output2Input62 14 28 44 82 41 2Output2Input101 13 13 35 35 54 54 42 42 21 2Output5"},{"iden":"note","content":""}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"Given a simple polygon with N vertices in counter-clockwise order, find the maximum number of non-zero area regions you can get by drawing one straight line through the origin.","has_page_source":false}