E. Polycarp and Arcolygon

Codeforces

IDCF10083E

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Polycarp has got a plane with N circles on it and an infinitely long thread. Each circle i is discribed using the centerpoint coordinates xi and yi and the radius ri. Polycarp uses the thread to swift all the circles so that all of them are inside the figure, formed by the thread. However, the thread can not be cut. Polycarp is eager to know what the shortest length the tread should be to be able to swift the circles and what area the resulting figure will have. The first line contains the only integer N, 2 ≤ N ≤ 100. Next N lines contain integer triplet xi, yi, ri. The numbers are separated by whitespaces, - 1000 ≤ xi, yi ≤ 1000, 1 ≤ ri ≤ 100. It is insured that the circles do not intersect and contact with each other. Output two numbers — thread length and figure area. You may assume that answers is coparated with the precision of 10 - 6. ## Input The first line contains the only integer N, 2 ≤ N ≤ 100.Next N lines contain integer triplet xi, yi, ri. The numbers are separated by whitespaces, - 1000 ≤ xi, yi ≤ 1000, 1 ≤ ri ≤ 100. It is insured that the circles do not intersect and contact with each other. ## Output Output two numbers — thread length and figure area. You may assume that answers is coparated with the precision of 10 - 6. [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of circles. For each $ i \in \{1, \dots, N\} $, let $ C_i = (x_i, y_i, r_i) $ denote a circle with center $ (x_i, y_i) \in \mathbb{R}^2 $ and radius $ r_i \in \mathbb{R}^+ $. **Constraints** 1. $ 2 \leq N \leq 100 $ 2. $ -1000 \leq x_i, y_i \leq 1000 $ 3. $ 1 \leq r_i \leq 100 $ 4. For all $ i \neq j $, the distance between centers satisfies $ \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \geq r_i + r_j $ (no intersection or tangency). **Objective** Compute: - The minimal length $ L $ of a closed thread enclosing all circles, equal to the perimeter of the convex hull of the union of the circles. - The area $ A $ of the region enclosed by the thread, equal to the area of the convex hull of the union of the circles. That is, let $ \mathcal{C} = \bigcup_{i=1}^N C_i $. Let $ H $ be the convex hull of $ \mathcal{C} $. Then: $$ L = \text{perimeter}(H), \quad A = \text{area}(H) $$

API Response (JSON)

{
  "problem": {
    "name": "E. Polycarp and Arcolygon",
    "description": {
      "content": "Polycarp has got a plane with N circles on it and an infinitely long thread. Each circle i is discribed using the centerpoint coordinates xi and yi and the radius ri. Polycarp uses the thread to swift",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10083E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has got a plane with N circles on it and an infinitely long thread. Each circle i is discribed using the centerpoint coordinates xi and yi and the radius ri. Polycarp uses the thread to swift...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of circles.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let $ C_i = (x_i, y_i, r_i) $ denote a circle with center $ (x_i, y_i) \\in \\mathbb{R}^2 $ and...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments