B. Gleb And Pizza

Codeforces

IDCF842B

Time2000ms

Memory256MB

Difficulty—

geometry

English · Original

Chinese · Translation

Formal · Original

Gleb ordered pizza home. When the courier delivered the pizza, he was very upset, because several pieces of sausage lay on the crust, and he does not really like the crust. The pizza is a circle of radius _r_ and center at the origin. Pizza consists of the main part — circle of radius _r_ - _d_ with center at the origin, and crust around the main part of the width _d_. Pieces of sausage are also circles. The radius of the _i_ -th piece of the sausage is _r__i_, and the center is given as a pair (_x__i_, _y__i_). Gleb asks you to help determine the number of pieces of sausage caught on the crust. A piece of sausage got on the crust, if it completely lies on the crust. ## Input First string contains two integer numbers _r_ and _d_ (0 ≤ _d_ < _r_ ≤ 500) — the radius of pizza and the width of crust. Next line contains one integer number _n_ — the number of pieces of sausage (1 ≤ _n_ ≤ 105). Each of next _n_ lines contains three integer numbers _x__i_, _y__i_ and _r__i_ ( - 500 ≤ _x__i_, _y__i_ ≤ 500, 0 ≤ _r__i_ ≤ 500), where _x__i_ and _y__i_ are coordinates of the center of _i_\-th peace of sausage, _r__i_ — radius of _i_\-th peace of sausage. ## Output Output the number of pieces of sausage that lay on the crust. [samples] ## Note Below is a picture explaining the first example. Circles of green color denote pieces of sausage lying on the crust. <center>![image](https://espresso.codeforces.com/f81223a0b6c596bd36f93cf97967395194e23ccd.png)</center>

Gleb 订了一份披萨。当快递员送达时，他非常沮丧，因为有几块香肠落在了饼皮上，而他并不喜欢饼皮。披萨是一个以原点为中心、半径为 $r$ 的圆。披萨由两部分组成：主部分——一个以原点为中心、半径为 $r - d$ 的圆，以及围绕主部分、宽度为 $d$ 的饼皮。香肠块也是圆形的。第 $i$ 块香肠的半径为 $r_i$，其中心坐标为 $(x_i, y_i)$。 Gleb 请你帮助确定有多少块香肠完全落在饼皮上。一块香肠落在饼皮上，当且仅当它完全位于饼皮区域内。第一行包含两个整数 $r$ 和 $d$ ($0 ≤ d < r ≤ 500$) —— 披萨的半径和饼皮的宽度。接下来一行包含一个整数 $n$ —— 香肠块的数量 ($1 ≤ n ≤ 10^5$)。接下来的 $n$ 行，每行包含三个整数 $x_i$, $y_i$ 和 $r_i$ ($-500 ≤ x_i, y_i ≤ 500$, $0 ≤ r_i ≤ 500$)，其中 $x_i$ 和 $y_i$ 是第 $i$ 块香肠的中心坐标，$r_i$ 是第 $i$ 块香肠的半径。请输出落在饼皮上的香肠块的数量。下图解释了第一个示例。绿色的圆表示位于饼皮上的香肠块。 ## Input 第一行包含两个整数 $r$ 和 $d$ ($0 ≤ d < r ≤ 500$) —— 披萨的半径和饼皮的宽度。接下来一行包含一个整数 $n$ —— 香肠块的数量 ($1 ≤ n ≤ 10^5$)。每行接下来的 $n$ 行包含三个整数 $x_i$, $y_i$ 和 $r_i$ ($-500 ≤ x_i, y_i ≤ 500$, $0 ≤ r_i ≤ 500$)，其中 $x_i$ 和 $y_i$ 是第 $i$ 块香肠的中心坐标，$r_i$ 是第 $i$ 块香肠的半径。 ## Output 请输出落在饼皮上的香肠块的数量。 [samples] ## Note 下图解释了第一个示例。绿色的圆表示位于饼皮上的香肠块。

**Definitions** Let $ r \in \mathbb{R}_{\geq 0} $ be the radius of the pizza. Let $ d \in \mathbb{R}_{\geq 0} $ be the width of the crust, with $ 0 \leq d < r $. Let $ n \in \mathbb{Z}^+ $ be the number of sausage pieces. For each $ i \in \{1, \dots, n\} $, let $ (x_i, y_i) \in \mathbb{R}^2 $ be the center and $ r_i \in \mathbb{R}_{\geq 0} $ be the radius of the $ i $-th sausage piece. **Constraints** 1. $ 0 \leq d < r \leq 500 $ 2. $ 1 \leq n \leq 10^5 $ 3. $ -500 \leq x_i, y_i \leq 500 $ 4. $ 0 \leq r_i \leq 500 $ **Objective** Count the number of sausage pieces $ i $ such that the entire sausage circle lies **completely on the crust**, i.e., $$ r - d \leq \sqrt{x_i^2 + y_i^2} - r_i \quad \text{and} \quad \sqrt{x_i^2 + y_i^2} + r_i \leq r $$ Equivalently: $$ r - d + r_i \leq \sqrt{x_i^2 + y_i^2} \leq r - r_i $$ (Note: The sausage lies entirely on the crust if it does not overlap the inner circle and does not extend beyond the outer pizza boundary.)

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Gleb And Pizza",
    "description": {
      "content": "Gleb ordered pizza home. When the courier delivered the pizza, he was very upset, because several pieces of sausage lay on the crust, and he does not really like the crust. The pizza is a circle of r",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF842B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Gleb ordered pizza home. When the courier delivered the pizza, he was very upset, because several pieces of sausage lay on the crust, and he does not really like the crust.\n\nThe pizza is a circle of r...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Gleb 订了一份披萨。当快递员送达时，他非常沮丧，因为有几块香肠落在了饼皮上，而他并不喜欢饼皮。\n\n披萨是一个以原点为中心、半径为 $r$ 的圆。披萨由两部分组成：主部分——一个以原点为中心、半径为 $r - d$ 的圆，以及围绕主部分、宽度为 $d$ 的饼皮。香肠块也是圆形的。第 $i$ 块香肠的半径为 $r_i$，其中心坐标为 $(x_i, y_i)$。\n\nGleb 请你帮助确定有多少块香肠...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ r \\in \\mathbb{R}_{\\geq 0} $ be the radius of the pizza.  \nLet $ d \\in \\mathbb{R}_{\\geq 0} $ be the width of the crust, with $ 0 \\leq d < r $.  \nLet $ n \\in \\mathbb{Z}^+ $ be th...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments