{"problem":{"name":"G. Affine","description":{"content":"We call a function f from  to  affine if it maps straight lines to straight lines. Formally, f is affine if and only if  for all  and . (Note that this is a weaker condition than linearity: f(x1, x2) ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10159G"},"statements":[{"statement_type":"Markdown","content":"We call a function f from  to  affine if it maps straight lines to straight lines. Formally, f is affine if and only if  for all  and . (Note that this is a weaker condition than linearity: f(x1, x2) = 3·x1 + 2·x2 + 1 is affine but not linear.)\n\nYou are given a polygon P in the plane. Determine the smallest integer m ≥ 0 such that there is an affine function f that maps the m-hypercube [0, 1m] to P, or determine that no such m exists.\n\nThe first line of the input contains the integer N (1 ≤ N ≤ 100'000), the number of given boundary points of the polygon. The i-th of the next N lines contains two integers Xi and Yi ( - 108 ≤ Xi, Yi ≤ 108), the coordinates of the i-th given boundary point of the polygon.\n\nThe counterclockwise boundary of the polygon P is obtained by connecting the given points by line segments. (Xi, Yi) is connected to (Xi + 1, Yi + 1) for 1 ≤ i < N, and (XN, YN) is connected to (X1, Y1). All given points are distinct and the boundary of the polygon P neither intersects nor touches itself.\n\nPrint _INFINITY_, if there is no m such that P is an affine image of the m-hypercube. Otherwise, print a single non-negative integer, the smallest m such that P is an affine image of the m-hypercube.\n\n## Input\n\nThe first line of the input contains the integer N (1 ≤ N ≤ 100'000), the number of given boundary points of the polygon. The i-th of the next N lines contains two integers Xi and Yi ( - 108 ≤ Xi, Yi ≤ 108), the coordinates of the i-th given boundary point of the polygon.The counterclockwise boundary of the polygon P is obtained by connecting the given points by line segments. (Xi, Yi) is connected to (Xi + 1, Yi + 1) for 1 ≤ i < N, and (XN, YN) is connected to (X1, Y1). All given points are distinct and the boundary of the polygon P neither intersects nor touches itself.\n\n## Output\n\nPrint _INFINITY_, if there is no m such that P is an affine image of the m-hypercube. Otherwise, print a single non-negative integer, the smallest m such that P is an affine image of the m-hypercube.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ P \\subset \\mathbb{R}^2 $ be a simple polygon with $ N $ vertices given in counterclockwise order: $ V = \\{(x_i, y_i) \\mid i = 1, \\dots, N\\} $.  \nLet $ [0,1]^m \\subset \\mathbb{R}^m $ denote the $ m $-dimensional unit hypercube.  \nAn affine function $ f: \\mathbb{R}^m \\to \\mathbb{R}^2 $ is of the form $ f(\\mathbf{u}) = A\\mathbf{u} + \\mathbf{b} $, where $ A \\in \\mathbb{R}^{2 \\times m} $, $ \\mathbf{b} \\in \\mathbb{R}^2 $.\n\n**Constraints**  \n1. $ 1 \\le N \\le 100{,}000 $  \n2. $ -10^8 \\le x_i, y_i \\le 10^8 $ for all $ i $  \n3. $ P $ is a simple polygon (non-self-intersecting, non-degenerate boundary).  \n\n**Objective**  \nFind the smallest integer $ m \\ge 0 $ such that there exists an affine function $ f: \\mathbb{R}^m \\to \\mathbb{R}^2 $ with $ f([0,1]^m) = P $.  \nIf no such $ m $ exists, output $ \\infty $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10159G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}