D. Archer's Shot

Codeforces

IDCF78D

Time2000ms

Memory256MB

Difficulty—

binary searchgeometrymathtwo pointers

English · Original

Chinese · Translation

Formal · Original

A breakthrough among computer games, "Civilization XIII", is striking in its scale and elaborate details. Let's take a closer look at one of them. The playing area in the game is split into congruent cells that are regular hexagons. The side of each cell is equal to 1. Each unit occupies exactly one cell of the playing field. The field can be considered infinite. Let's take a look at the battle unit called an "Archer". Each archer has a parameter "shot range". It's a positive integer that determines the radius of the circle in which the archer can hit a target. The center of the circle coincides with the center of the cell in which the archer stays. A cell is considered to be under the archer’s fire if and only if all points of this cell, including border points are located inside the circle or on its border. The picture below shows the borders for shot ranges equal to 3, 4 and 5. The archer is depicted as _A_. <center>![image](https://espresso.codeforces.com/357492d6c820da466bc70e64bbe7cc977eb72b68.png)</center>Find the number of cells that are under fire for some archer. ## Input The first and only line of input contains a single positive integer _k_ — the archer's shot range (1 ≤ _k_ ≤ 106). ## Output Print the single number, the number of cells that are under fire. Please do not use the _%lld_ specificator to read or write 64-bit integers in C++. It is preferred to use the _cout_ stream (also you may use the _%I64d_ specificator). [samples]

一款突破性的电脑游戏《文明十三》以其宏大的规模和精细的细节而引人注目。让我们仔细观察其中一个机制。游戏中的 playable 区域被划分为全等的正六边形单元格，每个单元格的边长为 1。每个单位恰好占据一个单元格。战场可视为无限大。让我们来看一种被称为“弓箭手”的战斗单位。每个弓箭手有一个参数“射程”，它是一个正整数，决定了弓箭手可以击中目标的圆形区域的半径。该圆的中心与弓箭手所在单元格的中心重合。一个单元格被认为是处于弓箭手的火力范围内，当且仅当该单元格的所有点（包括边界点）都位于该圆内或边界上。下图展示了射程分别为 #cf_span[3]、#cf_span[4] 和 #cf_span[5] 时的边界情况，弓箭手用 #cf_span[A] 表示。求出某个弓箭手的火力范围内的单元格数量。输入的第一行且唯一一行包含一个正整数 #cf_span[k] —— 弓箭手的射程（#cf_span[1 ≤ k ≤ 106]）。输出一个数字，即处于火力范围内的单元格数量。请不要在 C++ 中使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cout_ 流（也可以使用 _%I64d_ 标识符）。 ## Input 输入的第一行且唯一一行包含一个正整数 #cf_span[k] —— 弓箭手的射程（#cf_span[1 ≤ k ≤ 106]）。 ## Output 输出一个数字，即处于火力范围内的单元格数量。请不要在 C++ 中使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cout_ 流（也可以使用 _%I64d_ 标识符）。 [samples]

**Definitions** Let $ k \in \mathbb{Z}^+ $ be the shot range (radius of the circular firing zone). Let $ \mathcal{H} $ be the infinite hexagonal grid with cell side length 1, where each cell is a regular hexagon centered at points of a hexagonal lattice. A cell is *under fire* if and only if every point of the cell (including boundary) lies within or on the boundary of the circle of radius $ k $ centered at the archer’s cell. **Constraints** $ 1 \leq k \leq 10^6 $ **Objective** Compute the number of hexagonal cells entirely contained within or on the boundary of a circle of radius $ k $ centered at a hexagon center in the hexagonal lattice.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Archer's Shot",
    "description": {
      "content": "A breakthrough among computer games, \"Civilization XIII\", is striking in its scale and elaborate details. Let's take a closer look at one of them. The playing area in the game is split into congruent",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF78D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A breakthrough among computer games, \"Civilization XIII\", is striking in its scale and elaborate details. Let's take a closer look at one of them.\n\nThe playing area in the game is split into congruent...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一款突破性的电脑游戏《文明十三》以其宏大的规模和精细的细节而引人注目。让我们仔细观察其中一个机制。\n\n游戏中的 playable 区域被划分为全等的正六边形单元格，每个单元格的边长为 1。每个单位恰好占据一个单元格。战场可视为无限大。\n\n让我们来看一种被称为“弓箭手”的战斗单位。每个弓箭手有一个参数“射程”，它是一个正整数，决定了弓箭手可以击中目标的圆形区域的半径。该圆的中心与弓箭手所在单元格的中...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k \\in \\mathbb{Z}^+ $ be the shot range (radius of the circular firing zone).  \nLet $ \\mathcal{H} $ be the infinite hexagonal grid with cell side length 1, where each cell is a ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments