Задание 6
тема 1 из 1

Исполнитель Черепаха

Черепаха рисует на координатной плоскости: каждая команда меняет её координаты или направление, а цикл «Повтори» повторяет группу команд. Фигуры из прямоугольников задают границами по осям, и целые точки, площади и периметры пересечения и объединения считают по формулам. Фигуры с наклонными сторонами рисуют в Python модулем turtle с масштабом или проверяют каждую целую точку программой.

Главная тема в задании6На карте навыков

Как решать задачи про Черепаху

В начале Черепаха стоит в точке (0;0)(0; 0), её голова направлена вверх вдоль оси OyOy, хвост опущен. Опущенный хвост оставляет линию.

  • После каждой команды запишите координаты и направление. «Направо» поворачивает по часовой стрелке, «Налево» — против. «Назад» двигает Черепаху спиной вперёд без поворота.
  • Прямоугольник со сторонами по линиям сетки запишите границами: a≤x≤ba \le x \le b, c≤y≤dc \le y \le d.
  • Целые точки прямоугольника вместе с границей: (b−a+1)(d−c+1)(b - a + 1)(d - c + 1). Строго внутри: (b−a−1)(d−c−1)(b - a - 1)(d - c - 1).
  • Пересечение: по каждой оси от большей левой границы до меньшей правой. Объединение: NA∪B=NA+NB−NA∩BN_{A \cup B} = N_A + N_B - N_{A \cap B} — для точек, площадей и периметров.
  • Наклонные стороны: нарисуйте фигуру модулем turtle с масштабом и точками или найдите вершины через синус и косинус и проверьте каждую целую точку программой.

Команды Черепахи и её начальное положение

Исполнитель Черепаха движется по плоскости с осями OxOx и OyOy. «Вперёд nn» передвигает её на nn единиц туда, куда смотрит голова. «Назад nn» передвигает на nn единиц в обратную сторону, а голова смотрит туда же, куда и раньше. «Направо mm» поворачивает голову на mm градусов по часовой стрелке, «Налево mm» — против часовой стрелки. Поворот не меняет координаты.

Повороты на 360° складываются в целый оборот, поэтому «Направо 270» — то же, что «Налево 90», а «Налево 270» — то же, что «Направо 90». Отрицательное число меняет направление движения: «Назад −3» — то же, что «Вперёд 3». Нарисуйте путь на клетчатой бумаге и подпишите координаты каждой вершины.

Пример

Черепаха выполнила алгоритм Повтори 2 [Вперёд 8 Налево 90 Назад 15 Налево 90]. Какую фигуру она нарисовала?

OABC
Путь Черепахи: OO, AA, BB, CC и снова OO.
  1. 1.Голова смотрит вверх. «Вперёд 8»: точка A(0;8)A(0; 8).
  2. 2.«Налево 90»: голова смотрит влево. «Назад 15» двигает Черепаху вправо: точка B(15;8)B(15; 8).
  3. 3.«Налево 90»: голова смотрит вниз. Второй проход: «Вперёд 8» даёт C(15;0)C(15; 0), «Налево 90» поворачивает голову вправо, «Назад 15» возвращает Черепаху в O(0;0)O(0; 0).

Ответ: прямоугольник 0≤x≤150 \le x \le 15, 0≤y≤80 \le y \le 8

Цикл «Повтори» и замкнутая линия

Запись Повтори k [Команда1 … КомандаS] выполняет группу команд в скобках kk раз подряд. Цикл может стоять внутри другого цикла: тогда внутренний цикл целиком выполняется при каждом проходе внешнего.

Линия замыкается, когда сумма поворотов равна 360° и Черепаха вернулась в начальную точку. Если за один проход цикл Вперёд n Направо m поворачивает голову на mm градусов, то правильный многоугольник замкнётся за 360:m360 : m проходов. Лишние проходы идут по уже нарисованной линии и фигуру не меняют.

Пример

Черепаха выполнила алгоритм Повтори 11 [Вперёд 6 Направо 45]. Какую фигуру она нарисовала?

  1. 1.За один проход Черепаха рисует отрезок длины 6 и поворачивает на 45°.
  2. 2.360:45=8360 : 45 = 8: после восьми проходов голова смотрит вверх, а Черепаха снова в точке (0;0)(0; 0).
  3. 3.Проходы с 9-го по 11-й обводят три первые стороны ещё раз.

Ответ: правильный восьмиугольник со стороной 6

Поднятый хвост: где начинается вторая фигура

«Поднять хвост» переводит Черепаху в режим перемещения без рисования. Команды движения после неё только сдвигают Черепаху. «Опустить хвост» снова включает рисование. Так алгоритм рисует две фигуры: первая начинается в (0;0)(0; 0), вторая — в точке, куда Черепаха пришла с поднятым хвостом.

Следите и за направлением головы. Обычно перемещение заканчивается поворотом, который возвращает голову вверх, и вторая фигура строится так же, как первая. Иногда хвост поднят уже в начале: тогда линия начинается только после команды «Опустить хвост».

Пример

Алгоритм: Повтори 6 [Вперёд 24 Направо 90 Вперёд 30 Направо 90], Поднять хвост, Вперёд 2 Направо 90 Вперёд 10 Налево 90, Опустить хвост, Повтори 6 [Вперёд 75 Направо 90 Вперёд 71 Направо 90]. Задайте обе фигуры границами по осям.

  1. 1.Первый цикл: вверх 24, вправо 30, вниз 24, влево 30. Это прямоугольник 0≤x≤300 \le x \le 30, 0≤y≤240 \le y \le 24. Шесть проходов обводят его три раза.
  2. 2.Хвост поднят: «Вперёд 2» даёт (0;2)(0; 2), «Направо 90» и «Вперёд 10» дают (10;2)(10; 2), «Налево 90» возвращает голову вверх.
  3. 3.Второй цикл из точки (10;2)(10; 2): вверх 75, вправо 71. Это прямоугольник 10≤x≤8110 \le x \le 81, 2≤y≤772 \le y \le 77.

Ответ: 0≤x≤300 \le x \le 30, 0≤y≤240 \le y \le 24 и 10≤x≤8110 \le x \le 81, 2≤y≤772 \le y \le 77

Целые точки прямоугольника: с границей и без

Точка с целочисленными координатами — точка, у которой обе координаты целые. На отрезке a≤x≤ba \le x \le b лежат b−a+1b - a + 1 целых чисел, строго между aa и bb — b−a−1b - a - 1. Для прямоугольника a≤x≤ba \le x \le b, c≤y≤dc \le y \le d перемножьте число значений xx и число значений yy.

Если в вопросе «включая точки на границе», берите (b−a+1)(d−c+1)(b - a + 1)(d - c + 1). Если «точки на линии учитывать не следует», берите (b−a−1)(d−c−1)(b - a - 1)(d - c - 1). Ошибка на единицу в одном из множителей меняет ответ на целый ряд точек.

Пример

Черепаха нарисовала прямоугольник 0≤x≤50 \le x \le 5, 0≤y≤30 \le y \le 3. Сколько в нём целых точек вместе с границей и сколько строго внутри?

OABC
Точки строго внутри: 4 в ряду, 2 ряда.
  1. 1.С границей: xx от 0 до 5 — 6 значений, yy от 0 до 3 — 4 значения. 6⋅4=246 \cdot 4 = 24.
  2. 2.Строго внутри: xx от 1 до 4 — 4 значения, yy от 1 до 2 — 2 значения. 4⋅2=84 \cdot 2 = 8.

Ответ: 24 с границей, 8 строго внутри

Пересечение двух прямоугольников

Пересечение фигур — часть плоскости, которая принадлежит обеим фигурам. Пересечение прямоугольников a1≤x≤b1a_1 \le x \le b_1 и a2≤x≤b2a_2 \le x \le b_2 по оси xx — отрезок от max⁡(a1,a2)\max(a_1, a_2) до min⁡(b1,b2)\min(b_1, b_2). По оси yy — так же. Если левая граница получилась больше правой, фигуры не пересекаются.

Пересечение — снова прямоугольник. Его точки, площадь и периметр считают по его границам. «Точки на границах пересечения» — точки на сторонах этого прямоугольника.

Пример задания

Открытый банк ФИПИ

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм: 
Повтори 2 [Вперёд 21 Направо 90 Вперёд 27 Направо 90] 
Поднять хвост 
Вперёд 9 Направо 90 Вперёд 10 Налево 90 
Опустить хвост 
Повтори 2 [Вперёд 86 Направо 90 Вперёд 47 Направо 90]
Определите, сколько точек с целочисленными координатами будут находиться внутри области пересечения фигур, ограниченных заданными алгоритмом линиями, включая точки на границах этого пересечения.

Объединение: сложите и вычтите пересечение

Объединение фигур — часть плоскости, которая принадлежит хотя бы одной из них. Точки пересечения входят в обе фигуры, поэтому в сумме они посчитаны дважды: NA∪B=NA+NB−NA∩BN_{A \cup B} = N_A + N_B - N_{A \cap B}. Если фигуры не пересекаются, вычитать нечего.

Если один прямоугольник лежит внутри другого, объединение — большой прямоугольник. Тогда «точки на линиях» — точки на его сторонах, а стороны маленького прямоугольника проходят внутри объединения.

Программой точки считают перебором: для каждой целой точки проверьте условия «внутри первого» и «внутри второго» и сложите точки, где выполнено хотя бы одно.

Пример

Черепаха нарисовала прямоугольники 0≤x≤120 \le x \le 12, 0≤y≤90 \le y \le 9 и 4≤x≤94 \le x \le 9, −3≤y≤15-3 \le y \le 15. Сколько целых точек в их объединении, включая точки на линиях?

  1. 1.Первый: 13⋅10=13013 \cdot 10 = 130 точек. Второй: 6⋅19=1146 \cdot 19 = 114 точек.
  2. 2.Пересечение: 4≤x≤94 \le x \le 9, 0≤y≤90 \le y \le 9, это 6⋅10=606 \cdot 10 = 60 точек.
  3. 3.Объединение: 130+114−60=184130 + 114 - 60 = 184. Программа перебирает точки квадрата от −5-5 до 19 и печатает то же число.

Ответ: 184184

Площадь пересечения, объединения и суммарная площадь

Площадь прямоугольника a≤x≤ba \le x \le b, c≤y≤dc \le y \le d равна S=(b−a)(d−c)S = (b - a)(d - c): здесь считают клетки, а не точки, поэтому единицу не прибавляют. Площадь пересечения — площадь прямоугольника-пересечения. Площадь объединения: SA∪B=SA+SB−SA∩BS_{A \cup B} = S_A + S_B - S_{A \cap B}.

Суммарная площадь фигур — сумма их площадей SA+SBS_A + S_B. Общая часть в ней посчитана дважды. Не путайте её с площадью объединения.

Пример

Алгоритм: Повтори 2 [Вперёд 4 Направо 90 Вперёд 6 Направо 90], Поднять хвост, Вперёд 2 Направо 90 Вперёд 3 Налево 90, Опустить хвост, Повтори 2 [Вперёд 5 Направо 90 Вперёд 5 Направо 90]. Найдите площадь пересечения, площадь объединения и суммарную площадь фигур.

OP
Первый прямоугольник начинается в OO, второй — в PP. Пересечение закрашено.
  1. 1.Первая фигура: 0≤x≤60 \le x \le 6, 0≤y≤40 \le y \le 4, SA=6⋅4=24S_A = 6 \cdot 4 = 24.
  2. 2.Хвост поднят: Черепаха приходит в P(3;2)P(3; 2). Вторая фигура: 3≤x≤83 \le x \le 8, 2≤y≤72 \le y \le 7, SB=5⋅5=25S_B = 5 \cdot 5 = 25.
  3. 3.Пересечение: 3≤x≤63 \le x \le 6, 2≤y≤42 \le y \le 4, S=3⋅2=6S = 3 \cdot 2 = 6.
  4. 4.Объединение: 24+25−6=4324 + 25 - 6 = 43. Суммарная площадь: 24+25=4924 + 25 = 49.

Ответ: 6, 43 и 49

Периметр пересечения и объединения

Периметр прямоугольника a≤x≤ba \le x \le b, c≤y≤dc \le y \le d равен P=2((b−a)+(d−c))P = 2((b - a) + (d - c)). Пересечение — прямоугольник, его периметр считают по той же формуле. Периметр объединения — длина его внешней границы: PA∪B=PA+PB−PA∩BP_{A \cup B} = P_A + P_B - P_{A \cap B}. Формула верна, когда стороны фигур не лежат на одной линии.

Если квадраты только касаются сторонами, общий отрезок длины ll проходит внутри объединения. Тогда PA∪B=PA+PB−2lP_{A \cup B} = P_A + P_B - 2l. Пример: квадраты 6×66 \times 6 с общим отрезком длины 3 дают 24+24−6=4224 + 24 - 6 = 42. В сомнительном случае обойдите границу объединения на рисунке и сложите длины отрезков.

Пример

Черепаха нарисовала прямоугольники 0≤x≤120 \le x \le 12, 0≤y≤90 \le y \le 9 и 4≤x≤94 \le x \le 9, −3≤y≤15-3 \le y \le 15. Найдите периметр пересечения и периметр объединения.

  1. 1.PA=2(12+9)=42P_A = 2(12 + 9) = 42, PB=2(5+18)=46P_B = 2(5 + 18) = 46.
  2. 2.Пересечение: 4≤x≤94 \le x \le 9, 0≤y≤90 \le y \le 9, P=2(5+9)=28P = 2(5 + 9) = 28.
  3. 3.Объединение: 42+46−28=6042 + 46 - 28 = 60.

Ответ: 28 и 60

Рисунок в Python: модуль turtle, масштаб и точки

В Python есть модуль turtle с той же Черепахой. Команды переводятся так: «Вперёд nn» — forward(n * k), «Назад nn» — backward(n * k), «Направо mm» — right(m), «Налево mm» — left(m), «Поднять хвост» — up(), «Опустить хвост» — down(), «Повтори kk» — цикл for i in range(k):. Основы цикла — в теме цикл for.

Три отличия от задачи. Черепаха Python сначала смотрит вправо, поэтому первая строка рисунка — left(90). Один шаг равен одному пикселю, поэтому все длины умножают на масштаб kk, обычно 20–30. Чтобы рисунок появился сразу, пишут tracer(0) в начале и update() в конце, а done() оставляет окно открытым.

После рисунка поднимите хвост и поставьте точку dot(5) в каждой целой точке: goto(x * k, y * k). Точки внутри фигуры посчитайте по рядам. Точку, которая касается линии, проверьте расчётом.

Пример

Черепаха выполнила алгоритм Повтори 7 [Вперёд 10 Направо 120]. Сколько целых точек лежит внутри фигуры? Точки на линии не учитывайте.

  1. 1.360:120=3360 : 120 = 3: это правильный треугольник со стороной 10 и вершинами (0;0)(0; 0), (0;10)(0; 10), (8,66;5)(8{,}66; 5). Лишние проходы фигуру не меняют.
  2. 2.Программа рисует треугольник с масштабом 30 и ставит точки от −1-1 до 10 по обеим осям.
  3. 3.Считаем точки по столбцам x=1,2,…,8x = 1, 2, \ldots, 8: 9, 7, 7, 5, 5, 3, 1, 1. Точки на оси OyOy лежат на стороне.
  4. 4.Сомнительная точка (8;5)(8; 5): сторона в столбце x=8x = 8 проходит на высоте 8⋅tg⁡30∘≈4,628 \cdot \operatorname{tg} 30^\circ \approx 4{,}62 и 10−4,62=5,3810 - 4{,}62 = 5{,}38, точка между ними — внутри.
  5. 5.Всего 9+7+7+5+5+3+1+1=389 + 7 + 7 + 5 + 5 + 3 + 1 + 1 = 38.

Ответ: 3838

Координаты вершин через синус и косинус

Направление головы задают углом aa от оси OxOx против часовой стрелки. В начале a=90∘a = 90^\circ. «Направо mm» уменьшает угол: a−ma - m. «Налево mm» увеличивает: a+ma + m. «Вперёд nn» сдвигает Черепаху: x+ncos⁡ax + n \cos a, y+nsin⁡ay + n \sin a. «Назад nn» — то же с −n-n.

В Python cos и sin из модуля math принимают угол в радианах, поэтому пишут cos(radians(a)). Дробные координаты содержат погрешность в последних знаках, поэтому печатают round(x, 2). Функции forward и right ниже копят вершины в списке P.

Пример

Хвост поднят. Алгоритм: Вперёд 100 Направо 90 Вперёд 100 Направо 30, Опустить хвост, Повтори 10 [Вперёд 25 Направо 90]. Найдите вершины фигуры.

  1. 1.С поднятым хвостом Черепаха приходит в (100;100)(100; 100), голова смотрит вправо, a=0∘a = 0^\circ. После «Направо 30» угол a=−30∘a = -30^\circ.
  2. 2.Хвост опущен: список P начинается с точки (100;100)(100; 100).
  3. 3.Цикл: 360:90=4360 : 90 = 4, это квадрат со стороной 25, повёрнутый на 30°. Первые пять точек списка — четыре вершины и возврат в начало.

Ответ: (100;100)(100; 100), (121,65;87,5)(121{,}65; 87{,}5), (109,15;65,85)(109{,}15; 65{,}85), (87,5;78,35)(87{,}5; 78{,}35)

Точки строго внутри выпуклой фигуры

Фигура выпуклая, если она лежит по одну сторону от прямой каждой своей стороны: треугольник, квадрат, правильный шестиугольник. Сторону проходят от вершины (x1;y1)(x_1; y_1) к вершине (x2;y2)(x_2; y_2). Для точки (px;py)(p_x; p_y) считают d=(x2−x1)(py−y1)−(y2−y1)(px−x1)d = (x_2 - x_1)(p_y - y_1) - (y_2 - y_1)(p_x - x_1). Если d>0d > 0, точка слева от стороны, если d<0d < 0 — справа, если d=0d = 0 — на прямой стороны.

Черепаха обходит фигуру в одну сторону, поэтому точка строго внутри, если все dd одного знака и не равны нулю. Дробные координаты содержат погрешность, поэтому каждое dd сравнивают не с нулём, а с малым числом 1e-9.

Программа ниже сначала находит вершины так же, как в блоке координаты вершин, но без round: округление сдвигает вершины. Функция inside считает dd для каждой стороны. Потом программа перебирает все целые точки квадрата, в котором лежит фигура.

Пример задания

Открытый банк ФИПИ

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Направо m (где m - целое число), вызывающая изменение направления движения на m градусов
по часовой стрелке.
Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:
Повтори 18 [Вперёд 19 Направо 60].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

Невыпуклая фигура: части и вырез

Невыпуклую фигуру (уголок, прямоугольник с зубцами, звезду) разбейте на выпуклые части или представьте как большую фигуру без выреза. Целая точка внутри, если она лежит в одной из частей и не лежит на нарисованной линии. Стороны частей, которые проходят внутри фигуры, линией не являются.

В программе каждая часть — своё условие, а точки на линии отсекает отдельное условие. Для прямоугольных частей хватает сравнений координат.

Пример

Черепаха нарисовала замкнутую ломаную с вершинами (0;0)(0; 0), (10;0)(10; 0), (10;−10)(10; -10), (−10;−10)(-10; -10), (−10;10)(-10; 10), (0;10)(0; 10). Сколько целых точек лежит внутри фигуры? Точки на линии не учитывайте.

  1. 1.Фигура — квадрат −10≤x≤10-10 \le x \le 10, −10≤y≤10-10 \le y \le 10 без верхней правой четверти x≥0x \ge 0, y≥0y \ge 0.
  2. 2.Строго внутри большого квадрата: 19⋅19=36119 \cdot 19 = 361 точка.
  3. 3.Вырез: точки с x≥0x \ge 0 и y≥0y \ge 0 внутри большого квадрата, 10⋅10=10010 \cdot 10 = 100. Точки на отрезках x=0x = 0 и y=0y = 0 лежат на линии, они тоже уходят.
  4. 4.361−100=261361 - 100 = 261. Программа проверяет те же два условия.

Ответ: 261261

Исполнитель Цапля: команда «Дуга»

Исполнитель Цапля знает команды «Вперёд nn», «Направо mm» и «Дуга r,a,br, a, b». Из точки (x;y)(x; y) «Дуга» ведёт Цаплю по полуокружности радиуса rr с центром (x+a;y+b)(x + a; y + b) по часовой стрелке. Цапля приходит в точку (x+2a;y+2b)(x + 2a; y + 2b), а дуга выгнута влево от направления из начальной точки в конечную.

Целая точка лежит строго внутри полукруга с центром (cx;cy)(c_x; c_y), если (x−cx)2+(y−cy)2<r2(x - c_x)^2 + (y - c_y)^2 < r^2 и она лежит по нужную сторону от диаметра. Точка с равенством лежит на дуге. Фигура из многоугольника и полукругов — невыпуклая, её считают по частям: части и вырез.

Пример

Цапля выполнила алгоритм Повтори 7 [Дуга 4, 0, 4 Дуга 4, 4, 0 Дуга 4, 0, -4 Дуга 4, -4, 0]. Сколько целых точек лежит внутри фигуры? Точки на линии не учитывайте.

  1. 1.Дуги ведут Цаплю из (0;0)(0; 0) в (0;8)(0; 8), (8;8)(8; 8), (8;0)(8; 0) и обратно в (0;0)(0; 0). Линия замкнулась за один проход.
  2. 2.Каждая дуга выгнута наружу. Фигура — квадрат 0≤x≤80 \le x \le 8, 0≤y≤80 \le y \le 8 и четыре полукруга радиуса 4 на его сторонах. Стороны квадрата проходят внутри фигуры.
  3. 3.Квадрат с границей: 9⋅9=819 \cdot 9 = 81 точка. Четыре вершины квадрата — концы дуг, они на линии: остаётся 77.
  4. 4.Левый полукруг вне квадрата: при x=−1x = -1 и x=−2x = -2 по 7 точек, при x=−3x = -3 — 5 точек, всего 19. Четыре полукруга: 4⋅19=764 \cdot 19 = 76.
  5. 5.77+76=15377 + 76 = 153. Программа проверяет квадрат, четыре полукруга и вершины.

Ответ: 153153

Потренируйте навык

Все задания на этот навык

Решать