{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"First 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)"},{"iden":"output","content":"Output a single number P.The answer is considered correct if its relative or absolute error doesn't exceed 10 - 6."},{"iden":"examples","content":"Input4 20 010 010 100 105 -15 11Output60.000000000000000"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"You are given a polygon with N points and a polyline with M points. The polyline cuts through the polygon, splitting it into multiple smaller polygons. Find the total perimeter of all resulting polygons. The polyline starts and ends outside the polygon, and each of its segments intersects the polygon’s edges at most once. No polyline point lies on any polygon edge. Output the total perimeter with precision up to 1e-6.","has_page_source":false}