E. Slicing cheese

Codeforces

IDCF10074E

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

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. 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) Output a single number P. The answer is considered correct if its relative or absolute error doesn't exceed 10 - 6. ## Input 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) ## Output Output a single number P.The answer is considered correct if its relative or absolute error doesn't exceed 10 - 6. [samples]

**Definitions** Let $ 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 $. Let $ 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}} $. **Constraints** 1. $ 3 \leq N \leq 1000 $, $ 2 \leq M \leq 1000 $ 2. All vertices of $ P_{\text{poly}} $ and $ L $ are distinct. 3. No point of $ L $ lies on any edge of $ P_{\text{poly}} $. 4. Each segment of $ L $ intersects at most one edge of $ P_{\text{poly}} $, and transversally. **Objective** Compute 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 $. $$ P = \sum_{\text{resulting polygons } Q} \text{Perimeter}(Q) $$

API Response (JSON)

{
  "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 polygon...",
      "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 vert...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments