Карточки
Тесты
Главная
Курсы
Куратор
Подписка
6. Определение результатов работы алгоритма: #291629
Исполнитель Цапля действует на плоскости с декартовой системой координат.
Цапле был дан для исполнения следующий алгоритм:
Повтори 7 [Дуга 4, 0, 4 Дуга 4, 4, 0 Дуга 4, 0, -4 Дуга 4, -4, 0]
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.
В начальный момент Цапля находится в точке $(0;0)$.
Проследим выполнение четырёх команд одного повторения.
- Дуга 4, 0, 4: центр полуокружности — $(0;4)$, Цапля перемещается из $(0;0)$ в $(0;8)$.
- Дуга 4, 4, 0: центр — $(4;8)$, Цапля перемещается в $(8;8)$.
- Дуга 4, 0, -4: центр — $(8;4)$, Цапля перемещается в $(8;0)$.
- Дуга 4, -4, 0: центр — $(4;0)$, Цапля возвращается в $(0;0)$.
Полученная замкнутая линия состоит из четырёх полуокружностей радиуса $4$, построенных наружу от квадрата с вершинами $(0;0)$, $(0;8)$, $(8;8)$, $(8;0)$.
Остальные шесть повторений проводят ту же самую линию и не изменяют область.
В квадрате $0\leq x\leq8$, $0\leq y\leq8$ находится $9\cdot9=81$ точка с целочисленными координатами. Четыре угловые точки лежат на заданной линии, поэтому внутри области находятся $81-4=77$ точек квадрата.
Посчитаем точки в одной из четырёх полуокружностей, расположенные за пределами квадрата. Рассмотрим левую полуокружность: $x^2+(y-4)^2<16,\qquad x<0$.
- При $x=-1$ подходят $7$ значений $y$: от $1$ до $7$.
- При $x=-2$ также подходят $7$ значений $y$: от $1$ до $7$.
- При $x=-3$ подходят $5$ значений $y$: от $2$ до $6$.
- При $x=-4$ точка $(-4;4)$ лежит на линии и не учитывается.
Таким образом, в одной полуокружности находится $7+7+5=19$ дополнительных точек.
Полуокружностей четыре, поэтому общее количество точек равно $77+4\cdot19=77+76=153$.
20
