Черепаха рисует фигуры по алгоритму с повторениями. Нужно понять, какие фигуры получились, и посчитать точки с целыми координатами внутри, на линиях или в общей части.
Как читать алгоритм
Голова сначала смотрит вверх, по оси Oy.
Налево 270 — то же, что Направо 90.
Назад n — шаг против направления головы, голова не поворачивается.
«Повтори 2 [a, поворот 90, b, поворот 90]» — прямоугольник a × b.
Как считать точки
В прямоугольнике a × b (стороны вдоль осей) (a + 1)·(b + 1) целых точек вместе с границей.
Объединение: сумма минус общая часть.
Строго внутри: (a − 1)·(b − 1).
Как решить на компьютере
Модуль turtle: нарисовать фигуры с масштабом и поставить точки dot() в узлах сетки, затем посчитать по рисунку.
Или повторить команды в программе и перебрать точки, как в разборах.
Разобранные варианты
Сначала нарисуй фигуры на клетчатой бумаге и посчитай сам, потом открой разбор.
Вариант 1
объединение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на линиях.
Разбор
Шаг 1. Первая фигура. За одно повторение Черепаха проходит две стороны и поворачивается в сумме на 180°, поэтому «Повтори 2 […]» рисует прямоугольник: x от 0 до 9, y от -7 до 0.
Шаг 2. Перемещение без рисования переводит Черепаху в начало второй фигуры. Вторая фигура — тоже прямоугольник: x от -7 до 5, y от -6 до 4.
Шаг 3. Считаем точки. В прямоугольнике 9×7 лежит (9 + 1)·(7 + 1) = 80 точек, во втором — 143. Общая часть (на рисунке выделена) — x от 0 до 5, y от -6 до 0, в ней 42 точки. Объединение: 80 + 143 − 42 = 181.
Ответ: 181
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
DIRS = {0: (0, 1), 90: (1, 0), 180: (0, -1), 270: (-1, 0)} # направление -> шаг по x и y
x = y = d = 0 # Черепаха в начале координат, голова вверх (вдоль оси Oy)
pen = True
figs = [[(0, 0)]] # вершины каждой нарисованной фигуры
def move(n): # Вперёд n (для Назад n передаём -n)
global x, y
dx, dy = DIRS[d]
x, y = x + n * dx, y + n * dy
if pen:
figs[-1].append((x, y))
def turn(m): # Направо m (для Налево m передаём -m)
global d
d = (d + m) % 360
def pen_up():
global pen
pen = False
def pen_down():
global pen
pen = True
figs.append([(x, y)])
for _ in range(2):
move(-7)
turn(90)
move(9)
turn(-270)
pen_up()
move(-6)
turn(-90)
move(7)
turn(90)
pen_down()
for _ in range(2):
move(10)
turn(-90)
move(-12)
turn(-90)
# обе фигуры — прямоугольники со сторонами вдоль осей: запоминаем крайние координаты
rects = [(min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f)) for f in figs]
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
if any(x1 <= X <= x2 and y1 <= Y <= y2 for x1, x2, y1, y2 in rects):
count += 1
print(count)
Вариант 2
пересечение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 2 [Назад 17 Направо 90 Назад 6 Направо 90] Поднять хвост Назад 5 Направо 90 Назад 1 Налево 90 Опустить хвост Повтори 2 [Назад 14 Направо 90 Назад 13 Направо 90]
Определите, сколько точек с целочисленными координатами находятся внутри пересечения фигур, ограниченных заданными алгоритмом линиями, включая точки на границе пересечения.
Разбор
Шаг 1. Первая фигура. За одно повторение Черепаха проходит две стороны и поворачивается в сумме на 180°, поэтому «Повтори 2 […]» рисует прямоугольник: x от -6 до 0, y от -17 до 0.
Шаг 2. Перемещение без рисования переводит Черепаху в начало второй фигуры. Вторая фигура — тоже прямоугольник: x от -14 до -1, y от -19 до -5.
Шаг 3. Общая часть (выделена на рисунке): x от -6 до -1, y от -17 до -5. Точек в ней (5 + 1)·(12 + 1) = 78.
Ответ: 78
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
DIRS = {0: (0, 1), 90: (1, 0), 180: (0, -1), 270: (-1, 0)} # направление -> шаг по x и y
x = y = d = 0 # Черепаха в начале координат, голова вверх (вдоль оси Oy)
pen = True
figs = [[(0, 0)]] # вершины каждой нарисованной фигуры
def move(n): # Вперёд n (для Назад n передаём -n)
global x, y
dx, dy = DIRS[d]
x, y = x + n * dx, y + n * dy
if pen:
figs[-1].append((x, y))
def turn(m): # Направо m (для Налево m передаём -m)
global d
d = (d + m) % 360
def pen_up():
global pen
pen = False
def pen_down():
global pen
pen = True
figs.append([(x, y)])
for _ in range(2):
move(-17)
turn(90)
move(-6)
turn(90)
pen_up()
move(-5)
turn(90)
move(-1)
turn(-90)
pen_down()
for _ in range(2):
move(-14)
turn(90)
move(-13)
turn(90)
rects = [(min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f)) for f in figs]
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
if all(x1 <= X <= x2 and y1 <= Y <= y2 for x1, x2, y1, y2 in rects):
count += 1
print(count)
Вариант 3
треугольник · строго внутри
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 3 [Вперёд 13 Направо 120]
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.
Разбор
Шаг 1. Какая фигура. Поворот на 120° три раза даёт полный оборот, поэтому за 3 повторения Черепаха рисует равносторонний треугольник со стороной 13 и возвращается в начало.
Шаг 2. Где треугольник. Одна сторона лежит на оси Oy от (0; 0) до (0; 13), третья вершина — справа, на расстоянии a·√3/2 ≈ 11.26 от оси, на высоте 6.5.
Шаг 3. Считаем точки. Точки на оси Oy лежат на линии и не считаются. Для каждого x считаем целые y строго между двумя наклонными сторонами. Вручную это долго, поэтому удобно посчитать программой: точка внутри, если она лежит строго по одну сторону от каждой стороны треугольника.
Ответ: 66
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
from math import sin, cos, radians
x = y = 0.0
d = 0 # направление в градусах: 0 — вверх, по часовой стрелке
pts = [(0.0, 0.0)]
def move(n):
global x, y
x += n * sin(radians(d))
y += n * cos(radians(d))
pts.append((x, y))
def turn(m):
global d
d = (d + m) % 360
for _ in range(3):
move(13)
turn(120)
A, B, C = pts[0], pts[1], pts[2] # треугольник: первые три вершины (дальше Черепаха идёт по тем же линиям)
def side(P, Q, X, Y): # знак векторного произведения: с какой стороны от прямой PQ точка (X, Y)
return (Q[0] - P[0]) * (Y - P[1]) - (Q[1] - P[1]) * (X - P[0])
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
s = [side(A, B, X, Y), side(B, C, X, Y), side(C, A, X, Y)]
if all(v > 1e-9 for v in s) or all(v < -1e-9 for v in s): # строго по одну сторону от всех сторон
count += 1
print(count)
Вариант 4
объединение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на линиях.
Разбор
Шаг 1. Первая фигура. За одно повторение Черепаха проходит две стороны и поворачивается в сумме на 180°, поэтому «Повтори 2 […]» рисует прямоугольник: x от -11 до 0, y от -14 до 0.
Шаг 2. Перемещение без рисования переводит Черепаху в начало второй фигуры. Вторая фигура — тоже прямоугольник: x от -17 до -8, y от -2 до 4.
Шаг 3. Считаем точки. В прямоугольнике 11×14 лежит (11 + 1)·(14 + 1) = 180 точек, во втором — 70. Общая часть (на рисунке выделена) — x от -11 до -8, y от -2 до 0, в ней 12 точек. Объединение: 180 + 70 − 12 = 238.
Ответ: 238
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
DIRS = {0: (0, 1), 90: (1, 0), 180: (0, -1), 270: (-1, 0)} # направление -> шаг по x и y
x = y = d = 0 # Черепаха в начале координат, голова вверх (вдоль оси Oy)
pen = True
figs = [[(0, 0)]] # вершины каждой нарисованной фигуры
def move(n): # Вперёд n (для Назад n передаём -n)
global x, y
dx, dy = DIRS[d]
x, y = x + n * dx, y + n * dy
if pen:
figs[-1].append((x, y))
def turn(m): # Направо m (для Налево m передаём -m)
global d
d = (d + m) % 360
def pen_up():
global pen
pen = False
def pen_down():
global pen
pen = True
figs.append([(x, y)])
for _ in range(2):
move(-14)
turn(270)
move(11)
turn(-90)
pen_up()
move(-2)
turn(90)
move(-8)
turn(-90)
pen_down()
for _ in range(2):
move(6)
turn(270)
move(9)
turn(-90)
# обе фигуры — прямоугольники со сторонами вдоль осей: запоминаем крайние координаты
rects = [(min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f)) for f in figs]
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
if any(x1 <= X <= x2 and y1 <= Y <= y2 for x1, x2, y1, y2 in rects):
count += 1
print(count)
Вариант 5
точки на линиях
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами лежат на линиях, нарисованных Черепахой.
Разбор
Шаг 1. Первая фигура. За одно повторение Черепаха проходит две стороны и поворачивается в сумме на 180°, поэтому «Повтори 2 […]» рисует прямоугольник: x от 0 до 12, y от 0 до 17.
Шаг 2. Перемещение без рисования переводит Черепаху в начало второй фигуры. Вторая фигура — тоже прямоугольник: x от 3 до 8, y от -2 до 13.
Шаг 3. Точки на контуре прямоугольника a×b: 2·(a + b). Для первого 58, для второго 40. Контуры пересекаются в 2 точках — их посчитали дважды. Итого 58 + 40 − 2 = 96.
Ответ: 96
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
DIRS = {0: (0, 1), 90: (1, 0), 180: (0, -1), 270: (-1, 0)} # направление -> шаг по x и y
x = y = d = 0 # Черепаха в начале координат, голова вверх (вдоль оси Oy)
pen = True
figs = [[(0, 0)]] # вершины каждой нарисованной фигуры
def move(n): # Вперёд n (для Назад n передаём -n)
global x, y
dx, dy = DIRS[d]
x, y = x + n * dx, y + n * dy
if pen:
figs[-1].append((x, y))
def turn(m): # Направо m (для Налево m передаём -m)
global d
d = (d + m) % 360
def pen_up():
global pen
pen = False
def pen_down():
global pen
pen = True
figs.append([(x, y)])
for _ in range(2):
move(17)
turn(270)
move(-12)
turn(-90)
pen_up()
move(-2)
turn(90)
move(8)
turn(-90)
pen_down()
for _ in range(2):
move(15)
turn(270)
move(5)
turn(-90)
rects = [(min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f)) for f in figs]
def on_border(X, Y, r):
x1, x2, y1, y2 = r
inside = x1 <= X <= x2 and y1 <= Y <= y2
return inside and (X in (x1, x2) or Y in (y1, y2))
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
if any(on_border(X, Y, r) for r in rects):
count += 1
print(count)
Вариант 6
объединение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на линиях.
Разбор
Шаг 1. Первая фигура. За одно повторение Черепаха проходит две стороны и поворачивается в сумме на 180°, поэтому «Повтори 2 […]» рисует прямоугольник: x от -15 до 0, y от 0 до 17.
Шаг 2. Перемещение без рисования переводит Черепаху в начало второй фигуры. Вторая фигура — тоже прямоугольник: x от -27 до -10, y от 7 до 23.
Шаг 3. Считаем точки. В прямоугольнике 15×17 лежит (15 + 1)·(17 + 1) = 288 точек, во втором — 306. Общая часть (на рисунке выделена) — x от -15 до -10, y от 7 до 17, в ней 66 точек. Объединение: 288 + 306 − 66 = 528.
Ответ: 528
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
DIRS = {0: (0, 1), 90: (1, 0), 180: (0, -1), 270: (-1, 0)} # направление -> шаг по x и y
x = y = d = 0 # Черепаха в начале координат, голова вверх (вдоль оси Oy)
pen = True
figs = [[(0, 0)]] # вершины каждой нарисованной фигуры
def move(n): # Вперёд n (для Назад n передаём -n)
global x, y
dx, dy = DIRS[d]
x, y = x + n * dx, y + n * dy
if pen:
figs[-1].append((x, y))
def turn(m): # Направо m (для Налево m передаём -m)
global d
d = (d + m) % 360
def pen_up():
global pen
pen = False
def pen_down():
global pen
pen = True
figs.append([(x, y)])
for _ in range(2):
move(17)
turn(270)
move(15)
turn(-90)
pen_up()
move(7)
turn(-90)
move(10)
turn(90)
pen_down()
for _ in range(2):
move(16)
turn(90)
move(-17)
turn(-270)
# обе фигуры — прямоугольники со сторонами вдоль осей: запоминаем крайние координаты
rects = [(min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f)) for f in figs]
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
if any(x1 <= X <= x2 and y1 <= Y <= y2 for x1, x2, y1, y2 in rects):
count += 1
print(count)
Вариант 7
пересечение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами находятся внутри пересечения фигур, ограниченных заданными алгоритмом линиями, включая точки на границе пересечения.
Разбор
Шаг 1. Первая фигура. За одно повторение Черепаха проходит две стороны и поворачивается в сумме на 180°, поэтому «Повтори 2 […]» рисует прямоугольник: x от -13 до 0, y от 0 до 15.
Шаг 2. Перемещение без рисования переводит Черепаху в начало второй фигуры. Вторая фигура — тоже прямоугольник: x от -6 до 4, y от 10 до 24.
Шаг 3. Общая часть (выделена на рисунке): x от -6 до 0, y от 10 до 15. Точек в ней (6 + 1)·(5 + 1) = 42.
Ответ: 42
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
DIRS = {0: (0, 1), 90: (1, 0), 180: (0, -1), 270: (-1, 0)} # направление -> шаг по x и y
x = y = d = 0 # Черепаха в начале координат, голова вверх (вдоль оси Oy)
pen = True
figs = [[(0, 0)]] # вершины каждой нарисованной фигуры
def move(n): # Вперёд n (для Назад n передаём -n)
global x, y
dx, dy = DIRS[d]
x, y = x + n * dx, y + n * dy
if pen:
figs[-1].append((x, y))
def turn(m): # Направо m (для Налево m передаём -m)
global d
d = (d + m) % 360
def pen_up():
global pen
pen = False
def pen_down():
global pen
pen = True
figs.append([(x, y)])
for _ in range(2):
move(15)
turn(-270)
move(-13)
turn(90)
pen_up()
move(10)
turn(-90)
move(-4)
turn(90)
pen_down()
for _ in range(2):
move(14)
turn(-270)
move(-10)
turn(90)
rects = [(min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f)) for f in figs]
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
if all(x1 <= X <= x2 and y1 <= Y <= y2 for x1, x2, y1, y2 in rects):
count += 1
print(count)
Вариант 8
треугольник · строго внутри
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 6 [Вперёд 9 Направо 120]
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.
Разбор
Шаг 1. Какая фигура. Поворот на 120° три раза даёт полный оборот, поэтому за 3 повторения Черепаха рисует равносторонний треугольник со стороной 9 и возвращается в начало; остальные 3 повторения проходят по тем же линиям.
Шаг 2. Где треугольник. Одна сторона лежит на оси Oy от (0; 0) до (0; 9), третья вершина — справа, на расстоянии a·√3/2 ≈ 7.79 от оси, на высоте 4.5.
Шаг 3. Считаем точки. Точки на оси Oy лежат на линии и не считаются. Для каждого x считаем целые y строго между двумя наклонными сторонами. Вручную это долго, поэтому удобно посчитать программой: точка внутри, если она лежит строго по одну сторону от каждой стороны треугольника.
Ответ: 30
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
from math import sin, cos, radians
x = y = 0.0
d = 0 # направление в градусах: 0 — вверх, по часовой стрелке
pts = [(0.0, 0.0)]
def move(n):
global x, y
x += n * sin(radians(d))
y += n * cos(radians(d))
pts.append((x, y))
def turn(m):
global d
d = (d + m) % 360
for _ in range(6):
move(9)
turn(120)
A, B, C = pts[0], pts[1], pts[2] # треугольник: первые три вершины (дальше Черепаха идёт по тем же линиям)
def side(P, Q, X, Y): # знак векторного произведения: с какой стороны от прямой PQ точка (X, Y)
return (Q[0] - P[0]) * (Y - P[1]) - (Q[1] - P[1]) * (X - P[0])
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
s = [side(A, B, X, Y), side(B, C, X, Y), side(C, A, X, Y)]
if all(v > 1e-9 for v in s) or all(v < -1e-9 for v in s): # строго по одну сторону от всех сторон
count += 1
print(count)
Вариант 9
точки на линиях
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 2 [Вперёд 6 Направо 90 Назад 16 Налево 270] Поднять хвост Назад 11 Направо 90 Назад 10 Налево 90 Опустить хвост Повтори 2 [Вперёд 14 Направо 90 Назад 11 Направо 90]
Определите, сколько точек с целочисленными координатами лежат на линиях, нарисованных Черепахой.
Разбор
Шаг 1. Первая фигура. За одно повторение Черепаха проходит две стороны и поворачивается в сумме на 180°, поэтому «Повтори 2 […]» рисует прямоугольник: x от -16 до 0, y от 0 до 6.
Шаг 2. Перемещение без рисования переводит Черепаху в начало второй фигуры. Вторая фигура — тоже прямоугольник: x от -21 до -10, y от -11 до 3.
Шаг 3. Точки на контуре прямоугольника a×b: 2·(a + b). Для первого 44, для второго 50. Контуры пересекаются в 2 точках — их посчитали дважды. Итого 44 + 50 − 2 = 92.
Ответ: 92
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
DIRS = {0: (0, 1), 90: (1, 0), 180: (0, -1), 270: (-1, 0)} # направление -> шаг по x и y
x = y = d = 0 # Черепаха в начале координат, голова вверх (вдоль оси Oy)
pen = True
figs = [[(0, 0)]] # вершины каждой нарисованной фигуры
def move(n): # Вперёд n (для Назад n передаём -n)
global x, y
dx, dy = DIRS[d]
x, y = x + n * dx, y + n * dy
if pen:
figs[-1].append((x, y))
def turn(m): # Направо m (для Налево m передаём -m)
global d
d = (d + m) % 360
def pen_up():
global pen
pen = False
def pen_down():
global pen
pen = True
figs.append([(x, y)])
for _ in range(2):
move(6)
turn(90)
move(-16)
turn(-270)
pen_up()
move(-11)
turn(90)
move(-10)
turn(-90)
pen_down()
for _ in range(2):
move(14)
turn(90)
move(-11)
turn(90)
rects = [(min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f)) for f in figs]
def on_border(X, Y, r):
x1, x2, y1, y2 = r
inside = x1 <= X <= x2 and y1 <= Y <= y2
return inside and (X in (x1, x2) or Y in (y1, y2))
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
if any(on_border(X, Y, r) for r in rects):
count += 1
print(count)
Вариант 10
объединение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на линиях.
Разбор
Шаг 1. Первая фигура. За одно повторение Черепаха проходит две стороны и поворачивается в сумме на 180°, поэтому «Повтори 2 […]» рисует прямоугольник: x от 0 до 6, y от 0 до 16.
Шаг 2. Перемещение без рисования переводит Черепаху в начало второй фигуры. Вторая фигура — тоже прямоугольник: x от -3 до 2, y от 12 до 21.
Шаг 3. Считаем точки. В прямоугольнике 6×16 лежит (6 + 1)·(16 + 1) = 119 точек, во втором — 60. Общая часть (на рисунке выделена) — x от 0 до 2, y от 12 до 16, в ней 15 точек. Объединение: 119 + 60 − 15 = 164.
Ответ: 164
Решение на Python. Повторяем команды Черепахи, запоминаем вершины фигур и перебираем точки.
DIRS = {0: (0, 1), 90: (1, 0), 180: (0, -1), 270: (-1, 0)} # направление -> шаг по x и y
x = y = d = 0 # Черепаха в начале координат, голова вверх (вдоль оси Oy)
pen = True
figs = [[(0, 0)]] # вершины каждой нарисованной фигуры
def move(n): # Вперёд n (для Назад n передаём -n)
global x, y
dx, dy = DIRS[d]
x, y = x + n * dx, y + n * dy
if pen:
figs[-1].append((x, y))
def turn(m): # Направо m (для Налево m передаём -m)
global d
d = (d + m) % 360
def pen_up():
global pen
pen = False
def pen_down():
global pen
pen = True
figs.append([(x, y)])
for _ in range(2):
move(16)
turn(90)
move(6)
turn(90)
pen_up()
move(12)
turn(90)
move(2)
turn(-90)
pen_down()
for _ in range(2):
move(9)
turn(-90)
move(5)
turn(-90)
# обе фигуры — прямоугольники со сторонами вдоль осей: запоминаем крайние координаты
rects = [(min(p[0] for p in f), max(p[0] for p in f), min(p[1] for p in f), max(p[1] for p in f)) for f in figs]
count = 0
for X in range(-60, 61):
for Y in range(-60, 61):
if any(x1 <= X <= x2 and y1 <= Y <= y2 for x1, x2, y1, y2 in rects):
count += 1
print(count)
Для самостоятельного решения
Варианты 11–15 без разборов. Ответ можно проверить кнопкой.
Вариант 11
пересечение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами находятся внутри пересечения фигур, ограниченных заданными алгоритмом линиями, включая точки на границе пересечения.
Вариант 12
объединение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на линиях.
Вариант 13
треугольник · строго внутри
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 3 [Вперёд 17 Налево 120]
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.
Вариант 14
точки на линиях
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами лежат на линиях, нарисованных Черепахой.
Вариант 15
объединение фигур
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. У исполнителя существует 6 команд: Поднять хвост — переход к перемещению без рисования; Опустить хвост — переход в режим рисования; Вперёд n — передвижение на n единиц в том направлении, куда указывает голова; Назад n — передвижение в противоположном голове направлении; Направо m — поворот на m градусов по часовой стрелке; Налево m — поворот на m градусов против часовой стрелки. Запись Повтори k [Команда1 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на линиях.