G. Segments

Codeforces

IDCF10100G

Time1000ms

Memory20MB

Difficulty—

English · Original

Formal · Original

You are given N segments in the xOy plane. Find the shortest closed broken line that contains all the given segments. A closed broken line is defined as a series of segments A[1 - A[2]], A[2 - A[3]] ... A[K - 1 - A[K]], A[K - A[1]], where A is an array of points on the plane. The line can intersect itself. The first line contains T, the number of tests to follow. Then T tests follow. For each test, the first line contains an integer N(), followed by N lines, each describing a line segment by giving 4 real numbers, the x and y coordinates of the first end of the segment, and then the x and y coordinates of the second end of the segment. Your output file should contain T real numbers, representing the minimum length of the shortest closed broken line containing all the line segments. Your output should have a precision of 1.e - 6. ## Input The first line contains T, the number of tests to follow. Then T tests follow. For each test, the first line contains an integer N(), followed by N lines, each describing a line segment by giving 4 real numbers, the x and y coordinates of the first end of the segment, and then the x and y coordinates of the second end of the segment. ## Output Your output file should contain T real numbers, representing the minimum length of the shortest closed broken line containing all the line segments. Your output should have a precision of 1.e - 6. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let $ N_k \in \mathbb{Z} $ be the number of line segments, and let $ S_k = \{ \overline{p_{i}^{(k)} q_{i}^{(k)}} \mid i = 1, \dots, N_k \} $ be the set of segments, where $ p_i^{(k)}, q_i^{(k)} \in \mathbb{R}^2 $ are the endpoints of the $ i $-th segment. **Constraints** 1. $ 1 \le T \le \text{some bound} $ (not specified, but assumed finite) 2. For each $ k $, $ N_k \ge 1 $, and each segment is defined by two distinct points in $ \mathbb{R}^2 $. **Objective** For each test case $ k $, find the minimum total length of a closed polygonal chain $ A^{(k)} = (v_1, v_2, \dots, v_m, v_1) $ such that: - Each segment $ \overline{p_i^{(k)} q_i^{(k)}} \in S_k $ is entirely contained in the union of the edges of the chain. - The chain may self-intersect. - The length is $ \sum_{j=1}^{m} \| v_{j+1} - v_j \| $, with $ v_{m+1} = v_1 $. Compute: $$ L_k = \min \left\{ \sum_{j=1}^{m} \| v_{j+1} - v_j \| \;\middle|\; \bigcup_{j=1}^{m} \overline{v_j v_{j+1}} \supseteq \bigcup_{i=1}^{N_k} \overline{p_i^{(k)} q_i^{(k)}} \right\} $$ Output $ L_k $ for each test case $ k $, with precision $ 10^{-6} $.

API Response (JSON)

{
  "problem": {
    "name": "G. Segments",
    "description": {
      "content": "You are given N segments in the xOy plane. Find the shortest closed broken line that contains all the given segments. A closed broken line is defined as a series of segments A[1 - A[2]], A[2 - A[3]] .",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 20480
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10100G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given N segments in the xOy plane. Find the shortest closed broken line that contains all the given segments. A closed broken line is defined as a series of segments A[1 - A[2]], A[2 - A[3]] ....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ N_k \\in \\mathbb{Z} $ be the number of line segments, and let $ S_k = \\{ \\o...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments