C. A Colourful Prospect

Codeforces

IDCF933C

Time1000ms

Memory256MB

Difficulty—

geometrygraphs

English · Original

Chinese · Translation

Formal · Original

_Firecrackers scare Nian the monster, but they're wayyyyy too noisy! Maybe fireworks make a nice complement._ Little Tommy is watching a firework show. As circular shapes spread across the sky, a splendid view unfolds on the night of Lunar New Year's eve. A wonder strikes Tommy. How many regions are formed by the circles on the sky? We consider the sky as a flat plane. A region is a connected part of the plane with positive area, whose bound consists of parts of bounds of the circles and is a curve or several curves without self-intersections, and that does not contain any curve other than its boundaries. Note that exactly one of the regions extends infinitely. ## Input The first line of input contains one integer _n_ (1 ≤ _n_ ≤ 3), denoting the number of circles. The following _n_ lines each contains three space-separated integers _x_, _y_ and _r_ ( - 10 ≤ _x_, _y_ ≤ 10, 1 ≤ _r_ ≤ 10), describing a circle whose center is (_x_, _y_) and the radius is _r_. No two circles have the same _x_, _y_ and _r_ at the same time. ## Output Print a single integer — the number of regions on the plane. [samples] ## Note For the first example, <center>![image](https://espresso.codeforces.com/e6a24b8a7f19e3f3a0fb7c5e7eafb89db446afc0.png)</center>For the second example, <center>![image](https://espresso.codeforces.com/0e3f1931fa9c6c77a8be15a43f427dfc683bd90b.png)</center>For the third example, <center>![image](https://espresso.codeforces.com/793579ed08c4b41c8e0bc7e5aa0face8808882de.png)</center>

鞭炮能吓跑年兽，但它们实在太吵了！也许烟花是更好的选择。小汤米正在观看一场烟花表演。当圆形图案在夜空中绽放时，农历新年的夜晚呈现出壮丽的景象。汤米产生了一个疑问：天空中的圆能形成多少个区域？我们将天空视为一个平面。一个区域是平面上一个连通的、面积为正的部分，其边界由圆的边界部分构成，是一条或若干条无自交的曲线，且不包含任何其他曲线。注意，恰好有一个区域是无限延伸的。输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3])，表示圆的个数。接下来的 #cf_span[n] 行，每行包含三个用空格分隔的整数 #cf_span[x], #cf_span[y] 和 #cf_span[r] (#cf_span[ - 10 ≤ x, y ≤ 10], #cf_span[1 ≤ r ≤ 10])，描述一个圆心为 #cf_span[(x, y)]、半径为 #cf_span[r] 的圆。任意两个圆的 #cf_span[x], #cf_span[y] 和 #cf_span[r] 不会完全相同。请输出一个整数——平面上形成的区域数量。对于第一个示例，对于第二个示例，对于第三个示例， ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3])，表示圆的个数。接下来的 #cf_span[n] 行，每行包含三个用空格分隔的整数 #cf_span[x], #cf_span[y] 和 #cf_span[r] (#cf_span[ - 10 ≤ x, y ≤ 10], #cf_span[1 ≤ r ≤ 10])，描述一个圆心为 #cf_span[(x, y)]、半径为 #cf_span[r] 的圆。任意两个圆的 #cf_span[x], #cf_span[y] 和 #cf_span[r] 不会完全相同。 ## Output 请输出一个整数——平面上形成的区域数量。 [samples] ## Note 对于第一个示例，对于第二个示例，对于第三个示例，

**Definitions** Let $ n \in \mathbb{Z} $ be the number of circles, with $ 1 \leq n \leq 3 $. For each $ i \in \{1, \dots, n\} $, let $ C_i $ be a circle defined by center $ (x_i, y_i) \in \mathbb{R}^2 $ and radius $ r_i \in \mathbb{R}^+ $, where $ -10 \leq x_i, y_i \leq 10 $ and $ 1 \leq r_i \leq 10 $. All circles are distinct: $ (x_i, y_i, r_i) \neq (x_j, y_j, r_j) $ for $ i \neq j $. **Constraints** No two circles are identical. **Objective** Compute the number of connected regions $ R $ into which the plane is divided by the union of the circles $ \bigcup_{i=1}^n C_i $, where each region is a maximal connected component of $ \mathbb{R}^2 \setminus \bigcup_{i=1}^n C_i $ with positive area.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. A Colourful Prospect",
    "description": {
      "content": "_Firecrackers scare Nian the monster, but they're wayyyyy too noisy! Maybe fireworks make a nice complement._ Little Tommy is watching a firework show. As circular shapes spread across the sky, a spl",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF933C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Firecrackers scare Nian the monster, but they're wayyyyy too noisy! Maybe fireworks make a nice complement._\n\nLittle Tommy is watching a firework show. As circular shapes spread across the sky, a spl...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "鞭炮能吓跑年兽，但它们实在太吵了！也许烟花是更好的选择。\n\n小汤米正在观看一场烟花表演。当圆形图案在夜空中绽放时，农历新年的夜晚呈现出壮丽的景象。\n\n汤米产生了一个疑问：天空中的圆能形成多少个区域？我们将天空视为一个平面。一个区域是平面上一个连通的、面积为正的部分，其边界由圆的边界部分构成，是一条或若干条无自交的曲线，且不包含任何其他曲线。注意，恰好有一个区域是无限延伸的。\n\n输入的第一行包含一个...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of circles, with $ 1 \\leq n \\leq 3 $.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ C_i $ be a circle defined by center $ (x_i, y_i) \\in \\mathbb{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments