Question

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

У исполнителя есть две команды:
- **Вперёд *n*** — передвижение на *n* единиц в направлении головы;
- **Направо *m*** — поворот на *m* градусов по часовой стрелке.

Запись **Повтори *k* [Команда1 Команда2 ... КомандаS]** означает повторение последовательности команд *k* раз.

Черепахе дан алгоритм:

```
Направо 45
Повтори 3 [Направо 45 Вперёд 10 Направо 45]
Направо 315 Вперёд 10 Направо 90
Вперёд 20 Направо 90
Повтори 2 [Вперёд 10 Направо 90]
```

Определите количество точек с целочисленными координатами, находящихся **внутри** области, ограниченной линией, заданной алгоритмом. Точки на линии не учитываются.

Accepted Answer

261

Answer

Идея решения: выполнить алгоритм движения Черепахи, записать все координаты пройденного пути, построить многоугольник и применить формулу Пика для подсчёта внутренних целочисленных точек.

Реализуем алгоритм на Python, отслеживая координаты Черепахи при каждом движении:

```python
import math

# Начальные условия
x, y = 0, 0
angle = 90  # голова направлена вверх (вдоль оси Y)
path = [(x, y)]

# Направо 45
angle = (angle - 45) % 360

# Повтори 3 [Направо 45 Вперёд 10 Направо 45]
for _ in range(3):
    angle = (angle - 45) % 360
    rad = math.radians(angle)
    x += 10 * math.cos(rad)
    y += 10 * math.sin(rad)
    path.append((x, y))
    angle = (angle - 45) % 360

# Направо 315
angle = (angle - 315) % 360

# Вперёд 10
rad = math.radians(angle)
x += 10 * math.cos(rad)
y += 10 * math.sin(rad)
path.append((x, y))

# Направо 90
angle = (angle - 90) % 360

# Вперёд 20
rad = math.radians(angle)
x += 20 * math.cos(rad)
y += 20 * math.sin(rad)
path.append((x, y))

# Направо 90
angle = (angle - 90) % 360

# Повтори 2 [Вперёд 10 Направо 90]
for _ in range(2):
    rad = math.radians(angle)
    x += 10 * math.cos(rad)
    y += 10 * math.sin(rad)
    path.append((x, y))
    angle = (angle - 90) % 360

# Округляем координаты до целых (из-за погрешности вычислений)
path = [(round(px), round(py)) for px, py in path]

# Вычисляем площадь по формуле Шоелейса
def shoelace_area(vertices):
    n = len(vertices)
    area = 0
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i + 1) % n]
        area += x1 * y2 - x2 * y1
    return abs(area) / 2

# Считаем точки на границе
def count_boundary_points(vertices):
    count = 0
    n = len(vertices)
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i + 1) % n]
        dx = abs(x2 - x1)
        dy = abs(y2 - y1)
        count += math.gcd(dx, dy)
    return count

area = shoelace_area(path)
boundary = count_boundary_points(path)

# Формула Пика: S = I + B/2 - 1
# I = S - B/2 + 1
interior = int(area - boundary / 2 + 1)

print(interior)
```

Программа выполняет следующие шаги:

1. Отслеживает положение и направление Черепахи при выполнении каждой команды.
2. Накапливает координаты всех вершин многоугольника в список `path`.
3. Вычисляет площадь многоугольника по формуле Шоелейса.
4. Подсчитывает количество целочисленных точек на границе многоугольника, используя наибольший общий делитель для каждого отрезка.
5. Применяет формулу Пика: $I = S - \frac{B}{2} + 1$, где $I$ — количество внутренних точек, $S$ — площадь, $B$ — количество граничных точек.

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=269014)

Задание №6Алгоритмы и исполнителиЕГЭ по информатике