K. Krotek

Codeforces

IDCF10091K

Time6000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Mole Krotek from famous Czech animation movie lives underground on 2D-plane on the depth ε . Soon Krotek dug N tunnels for his new home. Each tunnel is the segment, given by coordinates of the endpoints. Tunnels can intersect each other only in the endpoint they share. No three endpoints are collinear. Now Krotek wants to link all tunnels to the one network, connecting some of the existing endpoints by the new tunnels. New tunnels can intersect other new tunnels or the existing ones only in the endpoint they share. Find out minimal total length of the new tunnels. First line of the input contains one integer N (1 ≤ N ≤ 1000) — number of existing tunnels. Each of the next N lines contain four integers (x1, y1, x2, y2) — coordinates of the endpoints of the one existing tunnel. Coordinates does not exceed 104 by absolute value. You may assume that tunnels does not intersect (except for case when they share a endpoint) and that no three endpoints are collinear. Print the minimum total length of the additional tunnels with absolute or relative error 10 - 6 or less. ## Input First line of the input contains one integer N (1 ≤ N ≤ 1000) — number of existing tunnels.Each of the next N lines contain four integers (x1, y1, x2, y2) — coordinates of the endpoints of the one existing tunnel. Coordinates does not exceed 104 by absolute value.You may assume that tunnels does not intersect (except for case when they share a endpoint) and that no three endpoints are collinear. ## Output Print the minimum total length of the additional tunnels with absolute or relative error 10 - 6 or less. [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of existing tunnels. Let $ E = \{ e_1, e_2, \dots, e_N \} $ be the set of existing tunnel segments, where each $ e_i = \overline{p_i q_i} $ is a line segment between two distinct points $ p_i, q_i \in \mathbb{R}^2 $. Let $ V = \{ v_1, v_2, \dots, v_m \} \subseteq \mathbb{R}^2 $ be the set of all distinct endpoints of the tunnels (i.e., $ V = \bigcup_{i=1}^N \{p_i, q_i\} $), with $ m \leq 2N $. **Constraints** 1. $ 1 \leq N \leq 1000 $ 2. Each coordinate is an integer with absolute value $ \leq 10^4 $. 3. Tunnels intersect only at shared endpoints (i.e., the graph formed by existing tunnels is a simple forest). 4. No three endpoints are collinear. **Objective** Find the minimum total length of additional line segments (edges) to be added between points in $ V $ such that the resulting graph is connected, and no two added segments intersect except possibly at shared endpoints. That is, find a minimum-weight spanning tree over the complete graph on vertex set $ V $, where edge weights are Euclidean distances, and edges may only be added between vertices in $ V $, with no geometric crossing constraints beyond endpoint-sharing (since non-crossing is guaranteed by MST in plane under general position). $$ \min_{T \in \mathcal{T}(V)} \sum_{(u,v) \in T} \|u - v\|_2 $$ where $ \mathcal{T}(V) $ is the set of all spanning trees on vertex set $ V $.

API Response (JSON)

{
  "problem": {
    "name": "K. Krotek",
    "description": {
      "content": "Mole Krotek from famous Czech animation movie lives underground on 2D-plane on the depth ε . Soon Krotek dug N tunnels for his new home. Each tunnel is the segment, given by coordinates of the endpoi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10091K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mole Krotek from famous Czech animation movie lives underground on 2D-plane on the depth ε .\n\nSoon Krotek dug N tunnels for his new home. Each tunnel is the segment, given by coordinates of the endpoi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of existing tunnels.  \nLet $ E = \\{ e_1, e_2, \\dots, e_N \\} $ be the set of existing tunnel segments, where each $ e_i = \\overline{p_i q_i} $ i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments