J. Рудольф и бомбы

Codeforces

IDCF10176J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Рудольф вновь разрабатывает компьютерную игру. На этот раз для победы в ней нужно защитить город, разделённый на квадратные клетки, от падения бомб. Каждая бомба имеет параметры X и Y — координаты клетки, в которую она упадёт, а также параметр R — радиус поражения. Считается, что клетка с координатами (X1, Y1) находится в зоне поражения бомбы, упавшей в клетку с координатами (X, Y), если выполняется неравенство |X - X1| + |Y - Y1| ≤ R. В настоящее время Рудольф пишет функцию, определяющую ущерб, нанесённый городу бомбами. Помогите Рудольфу определить суммарное количество клеток, которые оказались в зоне поражения хотя бы одной бомбы. Первая строка содержит целое число N (1 ≤ N ≤ 2000) — количество бомб. Следующие N строк описывают бомбы. Каждая из них содержит целые числа Xi, Yi и Ri ( - 109 ≤ Xi, Yi ≤ 109, 0 ≤ Ri ≤ 2000) — соответственно координаты падения и радиус взрыва i-й бомбы. Выведите одно целое число — суммарное количество клеток, которые оказались в зоне поражения хотя бы одной бомбы. Иллюстрация ко второму примеру: ## Входные Данные Первая строка содержит целое число N (1 ≤ N ≤ 2000) — количество бомб.Следующие N строк описывают бомбы. Каждая из них содержит целые числа Xi, Yi и Ri ( - 109 ≤ Xi, Yi ≤ 109, 0 ≤ Ri ≤ 2000) — соответственно координаты падения и радиус взрыва i-й бомбы. ## Выходные Данные Выведите одно целое число — суммарное количество клеток, которые оказались в зоне поражения хотя бы одной бомбы. ## Примеры Входные данные10 0 3Выходные данные25Входные данные20 0 11 0 1Выходные данные8 ## Примечание Иллюстрация ко второму примеру: [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of bombs. For each bomb $ i \in \{1, \dots, N\} $, let $ (X_i, Y_i) \in \mathbb{Z}^2 $ be its impact coordinates and $ R_i \in \mathbb{Z}_{\geq 0} $ its radius. **Constraints** 1. $ 1 \leq N \leq 2000 $ 2. $ -10^9 \leq X_i, Y_i \leq 10^9 $ 3. $ 0 \leq R_i \leq 2000 $ **Objective** Compute the cardinality of the union of all Manhattan-distance balls: $$ \left| \bigcup_{i=1}^{N} \left\{ (x, y) \in \mathbb{Z}^2 \mid |x - X_i| + |y - Y_i| \leq R_i \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "J. Рудольф и бомбы",
    "description": {
      "content": "Рудольф вновь разрабатывает компьютерную игру. На этот раз для победы в ней нужно защитить город, разделённый на квадратные клетки, от падения бомб. Каждая бомба имеет параметры X и Y — координаты кл",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10176J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Рудольф вновь разрабатывает компьютерную игру. На этот раз для победы в ней нужно защитить город, разделённый на квадратные клетки, от падения бомб.\n\nКаждая бомба имеет параметры X и Y — координаты кл...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of bombs.  \nFor each bomb $ i \\in \\{1, \\dots, N\\} $, let $ (X_i, Y_i) \\in \\mathbb{Z}^2 $ be its impact coordinates and $ R_i \\in \\mathbb{Z}_{\\g...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments