Codeforces Beta Round 70 (Div. 2) |
---|
Закончено |
Стратегическая компьютерная игра нового поколения «Civilization XIII» поражает своей масштабностью и проработанностью деталей. Рассмотрим, например, одну из них.
Игровое поле в игре разбито на правильные шестиугольники со стороной в 1 условную единицу. Пропорции юнитов в отношении карты близки к реальным, поэтому игровое поле можно считать бесконечной плоскостью. Каждый юнит занимает ровно одну шестиугольную ячейку игрового поля.
Рассмотрим боевого юнита «Лучник». Каждый лучник имеет параметр «дальность выстрела». Это некоторое натуральное число условных единиц, которое задает радиус круга, в пределах которого лучник может поразить цель. Центр этого круга совпадает с центром ячейки, в которой сейчас находится лучник. Считается, что некоторая ячейка находится под обстрелом лучника, если и только если все ее точки (включая граничные), находится внутри или на границе круга.
На картинке ниже показаны границы обстрела лучника для «дальностей выстрела» 3, 4 и 5. Сам лучник обозначен буквой A.
Определите, какое количество клеток находится под обстрелом для лучника.
Входные данные представляют из себя одно натуральное число k — дальность выстрела лучника (1 ≤ k ≤ 106).
Выведите единственное число — количество ячеек, которые находятся под обстрелом.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).
3
7
4
13
5
19
Название |
---|