C. Polycarp and Polygon

Codeforces

IDCF10083C

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Polycarp has N segments, where length of i-th one is ai. He wants to find the minimal radius R of a circle, such that we can construct a convex polygon from the segments, all vertexes of the polygon belongs to circumference of the circle, and center of the circle is inside the polygon. You should find that radius, if it is possible. The first line contains N — the number of segments (3 ≤ N ≤ 100). The second line contains N integer numbers ai — the lengthes of segments (1 ≤ ai ≤ 100). Output the minimal radius R. If it is not exists then output _-1_. You may assume that answers is coparated with the precision of 10 - 6. ## Input The first line contains N — the number of segments (3 ≤ N ≤ 100). The second line contains N integer numbers ai — the lengthes of segments (1 ≤ ai ≤ 100). ## Output Output the minimal radius R. If it is not exists then output _-1_. You may assume that answers is coparated with the precision of 10 - 6. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of segments, with $ 3 \leq n \leq 100 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive real numbers representing the lengths of the segments, where $ 1 \leq a_i \leq 100 $. **Constraints** 1. $ n \geq 3 $ 2. $ a_i > 0 $ for all $ i \in \{1, \dots, n\} $ 3. The segments must form a convex polygon inscribed in a circle with center inside the polygon. **Objective** Find the minimal radius $ R > 0 $ such that there exists a convex cyclic polygon with side lengths $ a_1, a_2, \dots, a_n $, inscribed in a circle of radius $ R $, and the center of the circle lies strictly inside the polygon. If no such $ R $ exists, output $ -1 $. The radius $ R $ must satisfy: $$ \sum_{i=1}^n \arcsin\left(\frac{a_i}{2R}\right) = \pi $$ with the condition that $ \frac{a_i}{2R} \leq 1 $ for all $ i $, and $ R \geq \frac{\max(a_i)}{2} $. Additionally, the polygon inequality must hold: $$ \max(a_i) < \sum_{j \neq i} a_j \quad \text{for all } i $$ (Otherwise, output $ -1 $.)

API Response (JSON)

{
  "problem": {
    "name": "C. Polycarp and Polygon",
    "description": {
      "content": "Polycarp has N segments, where length of i-th one is ai. He wants to find the minimal radius R of a circle, such that we can construct a convex polygon from the segments, all vertexes of the polygon b",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10083C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has N segments, where length of i-th one is ai. He wants to find the minimal radius R of a circle, such that we can construct a convex polygon from the segments, all vertexes of the polygon b...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of segments, with $ 3 \\leq n \\leq 100 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive real numbers representing the lengths o...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments