{"problem":{"name":"G. Game Design","description":{"content":"Carol enjoys playing with wooden games. The objective of the game that fascinates her the most is to tilt a maze, made out of $1 \" cm\"$-by-$1 \" cm\"$ blocks, in any of the four cardinal directions to m","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10248G"},"statements":[{"statement_type":"Markdown","content":"Carol enjoys playing with wooden games. The objective of the game that fascinates her the most is to tilt a maze, made out of $1 \" cm\"$-by-$1 \" cm\"$ blocks, in any of the four cardinal directions to move a ball to a hole in the centre at $(0, 0)$. As shown in the figure, once the $1 \" cm\"$ wide ball starts moving, it keeps going until either it runs into a wooden block, or it falls into the hole—whichever comes first.\n\nCarol is interested in designing a maze of her own, and like any good game designer she already has a fixed solution in mind. This is given as a sequence of tilt moves which must all be followed in order. If any move causes nothing to happen, for example, because the ball is up against a block in that direction or already in the hole, the solution does not count.\n\nThe ball can be placed anywhere to start. Carol will take care of adding a square border of blocks covering the rows and columns $10^9 + 1$ cells away from the centre in each direction.\n\nDesign a board which can be won by applying her sequence of moves.\n\nThe input consists of: \n\nIf it is possible to create a maze with the given solution, first output $x$ and $y$, the integer coordinates for the ball to start at. Then on the next line, output $n$, the number of blocks to use. On each of the remaining $n$ lines, output $s$ and $t$, the integer coordinates of a block.\n\nOtherwise, output \"_impossible_\".\n\nYou may use at most $n <= 10^4$ blocks. All coordinates used must be at most $10^9$ in absolute value. No coordinate pair may be the same as the centre or any other coordinate pair. If there are multiple valid solutions, you may output any one of them.\n\n## Input\n\nThe input consists of:   One line with a string $s$ consisting of only the characters \"_LRUD_\" ($1 <= | s | <= 20$), the sequence of moves. These characters correspond to the directions $-x, + x, + y, -y$ respectively. No two consecutive characters in $s$ are the same. \n\n## Output\n\nIf it is possible to create a maze with the given solution, first output $x$ and $y$, the integer coordinates for the ball to start at. Then on the next line, output $n$, the number of blocks to use. On each of the remaining $n$ lines, output $s$ and $t$, the integer coordinates of a block.Otherwise, output \"_impossible_\".You may use at most $n <= 10^4$ blocks. All coordinates used must be at most $10^9$ in absolute value. No coordinate pair may be the same as the centre or any other coordinate pair. If there are multiple valid solutions, you may output any one of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 3 \\leq n \\leq 2000 $, 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 in counter-clockwise order.\n\n**Constraints**  \nThe polygon is simple: vertices are distinct, and non-consecutive edges do not intersect or touch.\n\n**Objective**  \nFind the minimum radius $ r \\in \\mathbb{R}_{\\geq 0} $ such that the union of closed disks of radius $ r $ centered at each vertex $ v_i $ covers the entire polygonal region bounded by $ P $.  \nThat is,  \n$$\n\\bigcup_{i=1}^n D(v_i, r) \\supseteq \\text{conv}(P)\n$$  \nwhere $ D(v_i, r) = \\{ p \\in \\mathbb{R}^2 \\mid \\|p - v_i\\| \\leq r \\} $, and $ \\text{conv}(P) $ denotes the polygonal region.\n\nThe minimal such $ r $ is the smallest value for which every point in the polygon lies within distance $ r $ of at least one vertex.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10248G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}