{"problem":{"name":"E. Slicing cheese","description":{"content":"You have a polygon defined by N points (xi, yi) and a polyline defined by M points (aj, bj). Polyline cuts polygon into some number of smaller polygons. Find the total perimeter P of resulting polygon","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10074E"},"statements":[{"statement_type":"Markdown","content":"You have a polygon defined by N points (xi, yi) and a polyline defined by M points (aj, bj). Polyline cuts polygon into some number of smaller polygons. Find the total perimeter P of resulting polygons. Polyline is guaranteed to start and end outside of the polygon. Each segment of polyline has no more than 1 common point with any segment of polygon segments. All points in the input are distinct. (aj, bj) does not lie on any line segment of the polygon.\n\nFirst line contains integers N and M. (3 ≤ N ≤ 1000, 2 ≤ M ≤ 1000)\n\nNext N lines contain integers xi and yi.\n\nNext M lines contain integers aj and bj.\n\n( - 105 ≤ xi, yi, aj, bj ≤ 105)\n\nOutput a single number P.\n\nThe answer is considered correct if its relative or absolute error doesn't exceed 10 - 6.\n\n## Input\n\nFirst line contains integers N and M. (3 ≤ N ≤ 1000, 2 ≤ M ≤ 1000)Next N lines contain integers xi and yi.Next M lines contain integers aj and bj.( - 105 ≤ xi, yi, aj, bj ≤ 105)\n\n## Output\n\nOutput a single number P.The answer is considered correct if its relative or absolute error doesn't exceed 10 - 6.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ P_{\\text{poly}} = (v_1, v_2, \\dots, v_N) $ be a simple polygon with vertices $ v_i = (x_i, y_i) \\in \\mathbb{R}^2 $.  \nLet $ L = (p_1, p_2, \\dots, p_M) $ be a polyline with vertices $ p_j = (a_j, b_j) \\in \\mathbb{R}^2 $, such that $ p_1 $ and $ p_M $ lie outside $ P_{\\text{poly}} $, and each segment $ \\overline{p_j p_{j+1}} $ intersects $ P_{\\text{poly}} $ in at most one point, which is not a vertex of $ P_{\\text{poly}} $.\n\n**Constraints**  \n1. $ 3 \\leq N \\leq 1000 $, $ 2 \\leq M \\leq 1000 $  \n2. All vertices of $ P_{\\text{poly}} $ and $ L $ are distinct.  \n3. No point of $ L $ lies on any edge of $ P_{\\text{poly}} $.  \n4. Each segment of $ L $ intersects at most one edge of $ P_{\\text{poly}} $, and transversally.\n\n**Objective**  \nCompute the total perimeter $ P $ of all connected components of $ P_{\\text{poly}} \\setminus L $, i.e., the union of the boundaries of the polygons formed by cutting $ P_{\\text{poly}} $ along $ L $.  \n\n$$\nP = \\sum_{\\text{resulting polygons } Q} \\text{Perimeter}(Q)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10074E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}