{"problem":{"name":"B. Battle Mage","description":{"content":"Battle mage Va Sya bought a silver plate with form of convex polygon with n vertices to practice his spells. Then he glued the plate on the thin glass of same form and shape, put this plate as a targ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10091B"},"statements":[{"statement_type":"Markdown","content":"Battle mage Va Sya bought a silver plate with form of convex polygon with n vertices to practice his spells.\n\nThen he glued the plate on the thin glass of same form and shape, put this plate as a target and started his practice. Today Va Sya practices a spell which makes a perfect circular hole in the plate itself, but keeps the glass untouched. Note that circles may overlap.\n\nAfter Va Sya ended up his practice session, he noticed, that all circles from the spells lied inside the plate (but may touch it's edge).\n\nThen he decided to hang the whole construction (glass with remaining parts of silver plate) on the door using selected vertex, so it can rotate freely around this vertex until it is stable.\n\nFind the final coordinates of vertices of the plate, if glass is so thin that its weight must be considered as zero.\n\nFirst line of the input contains three integers n, c and v (1 ≤ n ≤ 700, 1 ≤ c ≤ 2000, 1 ≤ v ≤ n) — number of vertices in the polygon, number of spells casted by Va Sya and 1-based number of the vertice he used to hang the remaining plate.\n\ni-th of next n lines contains two integers xi and yi — coordinates of the i-th vertice ( - 104 ≤ xi, yi ≤ 104). Vertices are listed in counterclockwise order.\n\nEach of next c lines contains three integers cxi, cyi and ri — coordinates of center and radius of one circle. It is guaranteed that all circles are non-degenerated and lie inside the polygon (possibly touches it's edge).\n\nPrint n lines, i-th of then containing x and y — final coordinates of i-th vertice with absolute error 10 - 5 or less. Vertices must be listed in same order as in the input file.\n\n## Input\n\nFirst line of the input contains three integers n, c and v (1 ≤ n ≤ 700, 1 ≤ c ≤ 2000, 1 ≤ v ≤ n) — number of vertices in the polygon, number of spells casted by Va Sya and 1-based number of the vertice he used to hang the remaining plate.i-th of next n lines contains two integers xi and yi — coordinates of the i-th vertice ( - 104 ≤ xi, yi ≤ 104). Vertices are listed in counterclockwise order.Each of next c lines contains three integers cxi, cyi and ri — coordinates of center and radius of one circle. It is guaranteed that all circles are non-degenerated and lie inside the polygon (possibly touches it's edge).\n\n## Output\n\nPrint n lines, i-th of then containing x and y — final coordinates of i-th vertice with absolute error 10 - 5 or less. Vertices must be listed in same order as in the input file.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices of a convex polygon.  \nLet $ c \\in \\mathbb{Z}^+ $ be the number of circular holes.  \nLet $ v \\in \\{1, \\dots, n\\} $ be the 1-based index of the vertex used as the pivot.  \n\nLet $ P = (p_1, p_2, \\dots, p_n) $, where $ p_i = (x_i, y_i) \\in \\mathbb{R}^2 $, be the vertices of the polygon in counterclockwise order.  \nLet $ C = \\{(c_x^j, c_y^j, r_j) \\mid j \\in \\{1, \\dots, c\\}\\} $ be the set of circular holes, each defined by center $ (c_x^j, c_y^j) \\in \\mathbb{R}^2 $ and radius $ r_j > 0 $, all entirely contained within the polygon (including boundary).  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 700 $, $ 1 \\leq c \\leq 2000 $, $ 1 \\leq v \\leq n $  \n2. $ -10^4 \\leq x_i, y_i \\leq 10^4 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. All circles lie inside the polygon (may touch the boundary).  \n\n**Objective**  \nCompute the final coordinates of the polygon vertices after removing the union of all circular holes and rotating the resulting shape freely around vertex $ p_v $ until it reaches a stable equilibrium under gravity (with glass weight negligible).  \n\nAssume the remaining silver plate is a rigid body with uniform density. The stable orientation occurs when the center of mass of the remaining plate lies **directly below** the pivot vertex $ p_v $.  \n\nLet $ M \\subset \\mathbb{R}^2 $ be the region of the polygon minus the union of all circular disks:  \n$$ M = \\text{Conv}(P) \\setminus \\bigcup_{j=1}^{c} \\mathcal{D}((c_x^j, c_y^j), r_j) $$  \nwhere $ \\mathcal{D}(q, r) $ denotes the closed disk centered at $ q $ with radius $ r $.  \n\nLet $ \\text{COM}(M) = (x_{\\text{com}}, y_{\\text{com}}) \\in \\mathbb{R}^2 $ be the center of mass of region $ M $.  \n\nLet $ \\theta \\in [0, 2\\pi) $ be the unique rotation angle (clockwise) about $ p_v $ such that the vector $ \\text{COM}(M) - p_v $ becomes vertically downward (i.e., aligned with $ (0, -1) $).  \n\nCompute the rotated positions of all vertices $ p_i' $ under this rotation:  \n$$ p_i' = R_{\\theta}(p_i - p_v) + p_v $$  \nwhere $ R_{\\theta} $ is the clockwise rotation matrix:  \n$$ R_{\\theta} = \\begin{bmatrix} \\cos\\theta & \\sin\\theta \\\\ -\\sin\\theta & \\cos\\theta \\end{bmatrix} $$  \n\nOutput $ p_1', p_2', \\dots, p_n' $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10091B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}