Карточки
Тесты
Главная
Курсы
Куратор
Подписка
6. Определение результатов работы алгоритма: #291624
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии.
Чертёжнику, находящемуся в начале координат (точке $(0,0)$), был дан для исполнения следующий алгоритм:
Сместиться на $(10,-1)$
Повтори 3 раза
Сместиться на $(-1,3)$
Сместиться на $(-2,-2)$
Конец
После выполнения алгоритма Чертёжник вернулся в исходную точку.
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом и линией, по которой Чертёжник вернулся в исходную точку. Точки на линии учитывать не следует.
Проследим за перемещением Чертёжника.
Сначала он перемещается из точки $(0,0)$ в точку
$(0,0)+(10,-1)=(10,-1)$.
Далее трижды выполняются две команды:
- Первое повторение:$(10,-1)\rightarrow(9,2)\rightarrow(7,0)$.
- Второе повторение:$(7,0)\rightarrow(6,3)\rightarrow(4,1)$.
- Третье повторение:$(4,1)\rightarrow(3,4)\rightarrow(1,2)$.
Затем Чертёжник возвращается по прямой из точки $(1,2)$ в исходную точку $(0,0)$.
Получена фигура с вершинами $(0,0)$, $(10,-1)$, $(9,2)$, $(7,0)$, $(6,3)$, $(4,1)$, $(3,4)$, $(1,2)$.
Найдём её площадь по формуле площади многоугольника: $S=\dfrac{|69-24|}{2}=\dfrac{45}{2}=22{,}5$.
Для применения формулы Пика определим количество целочисленных точек на границе. Для отрезка с приращениями $(\Delta x,\Delta y)$ количество промежутков между целочисленными точками равно $\gcd(|\Delta x|,|\Delta y|)$.
Для сторон фигуры получаем: $1+1+2+1+2+1+2+1=11$.
Таким образом, на границе находится $B=11$ целочисленных точек.
По формуле Пика $S=I+\dfrac{B}{2}-1$, где $I$ — количество целочисленных точек внутри фигуры.
$I=S-\dfrac{B}{2}+1=22{,}5-\dfrac{11}{2}+1=18$.
20
