Карточки
Тесты
Главная
Курсы
Куратор
Подписка
6. Определение результатов работы алгоритма: #291622
Чертёжнику, находящемуся в начале координат (точке $(0, 0)$), был дан для исполнения следующий алгоритм:
Сместиться на ($5, 6$)
Повтори $3$ раз
Сместиться на ($-1, -2$)
Сместиться на ($3, 3$)
Конец
Сместиться на ($-5, 0$)
После выполнения алгоритма Чертёжник вернулся в исходную точку.
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом и линией, по которой Чертёжник вернулся в исходную точку. Точки на линии учитывать не следует.
Выпишем последовательно координаты вершин:
- $(0,0)\rightarrow(5,6)$;
- первое повторение:
$(5,6)\rightarrow(4,4)\rightarrow(7,7)$; - второе повторение:
$(7,7)\rightarrow(6,5)\rightarrow(9,8)$; - третье повторение:
$(9,8)\rightarrow(8,6)\rightarrow(11,9)$; - после последней команды:
$(11,9)\rightarrow(6,9)$.
Затем фигура замыкается отрезком от $(6,9)$ до $(0,0)$.
Площадь многоугольника по формуле координат: $S=\dfrac12|356-323|=\dfrac{33}{2}=16{,}5$.
Количество целочисленных точек на границе найдём с помощью суммирования значений $\gcd(|\Delta x|,|\Delta y|)$ для всех сторон: $B=1+1+3+1+3+1+3+5+3=21$.
По формуле Пика $S=I+\dfrac B2-1$, где $I$ — количество целочисленных точек внутри фигуры.
$I=16{,}5-\dfrac{21}{2}+1=7$.
20
