Найти число целых клеток в окружности

Question

Есть окружность, которая нарисована в клетчатой тетради с радиусом R клеток, (R - целое число) . Нужно найти число клеток, находящихся целиком внутри окружности.

Answer 1

Весьма древня задача, никакой формулы нет. Скорей всего, формулировка спёрта с одного из конкурсов программистов, проходивших в конце 70-х - середине 80 годов. Решение сводится к простому перебору точек в одном из восьми полусегментов, остающихся снаружи вписанного квадрата. Имеются 4 варианта такого перебора, отличающихся друг от друга по скорости процентов на 10.
В том конкурсе я участвовал, но не победил