L. Inscribed Circle

Codeforces

IDCF10221L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given two circles on a plane. It is guaranteed that their circumferences have exactly two common points. The result of the intersection of two circles is a figure with the positive area consisting of points belonging to both circles. You have to inscribe a circle of the maximal possible radius into this figure. Output the coordinates of its center and its radius. The first line contains three integers $x_1$, $y_1$, $r_1$ ($-1000 <= x_1, y_1 <= 1000, 1 <= r_1 <= 1000$) — coordinates of the center of the first circle and its radius. The second line contains three integers $x_2$, $y_2$, $r_2$ ($-1000 <= x_2, y_2 <= 1000, 1 <= r_2 <= 1000$) — coordinates of the center of the second circle and its radius. Output three real numbers $x$, $y$, $r$ — coordinates of the center and radius of the resulting circle. Each of the printed numbers should have absolute or relative error not exceeding $10^(-9)$. ## Input The first line contains three integers $x_1$, $y_1$, $r_1$ ($-1000 <= x_1, y_1 <= 1000, 1 <= r_1 <= 1000$) — coordinates of the center of the first circle and its radius.The second line contains three integers $x_2$, $y_2$, $r_2$ ($-1000 <= x_2, y_2 <= 1000, 1 <= r_2 <= 1000$) — coordinates of the center of the second circle and its radius. ## Output Output three real numbers $x$, $y$, $r$ — coordinates of the center and radius of the resulting circle. Each of the printed numbers should have absolute or relative error not exceeding $10^(-9)$. [samples]

**Definitions** Let $ C_1 = (x_1, y_1, r_1) $ and $ C_2 = (x_2, y_2, r_2) $ be two circles in $ \mathbb{R}^2 $, with centers $ (x_1, y_1) $, $ (x_2, y_2) $ and radii $ r_1, r_2 > 0 $, respectively. Let $ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $ be the distance between centers. Given: $ |r_1 - r_2| < d < r_1 + r_2 $ (circumferences intersect at exactly two points). Let $ R $ be the intersection region: $ R = \overline{B}((x_1, y_1), r_1) \cap \overline{B}((x_2, y_2), r_2) $, where $ \overline{B}(c, r) $ denotes the closed disk centered at $ c $ with radius $ r $. **Objective** Find the circle $ C = (x, y, r) $ of maximal radius $ r $ such that $ C \subseteq R $. Output: $ (x, y, r) $, where $ (x, y) $ is the center and $ r $ is the radius of this maximal inscribed circle. **Solution** The maximal inscribed circle in the intersection of two disks is centered on the line segment joining the two centers, and its radius is determined by the geometry of the lens-shaped intersection. Let $ \vec{v} = (x_2 - x_1, y_2 - y_1) $. The center lies along the line connecting $ (x_1, y_1) $ and $ (x_2, y_2) $, at a point dividing the segment in the ratio of the radii. The radius $ r $ of the maximal inscribed circle is given by: $$ r = \frac{r_1 + r_2 - d}{2} $$ The center $ (x, y) $ lies on the line segment between $ (x_1, y_1) $ and $ (x_2, y_2) $, at distance $ r_1 - r $ from $ (x_1, y_1) $: $$ (x, y) = \left( x_1 + \frac{r_1 - r}{d} (x_2 - x_1),\ y_1 + \frac{r_1 - r}{d} (y_2 - y_1) \right) $$

API Response (JSON)

{
  "problem": {
    "name": "L. Inscribed Circle",
    "description": {
      "content": "You are given two circles on a plane. It is guaranteed that their circumferences have exactly two common points. The result of the intersection of two circles is a figure with the positive area consi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10221L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two circles on a plane. It is guaranteed that their circumferences have exactly two common points.\n\nThe result of the intersection of two circles is a figure with the positive area consi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ C_1 = (x_1, y_1, r_1) $ and $ C_2 = (x_2, y_2, r_2) $ be two circles in $ \\mathbb{R}^2 $, with centers $ (x_1, y_1) $, $ (x_2, y_2) $ and radii $ r_1, r_2 > 0 $, respectively. ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments