Статья Автор: Лебедев Дмитрий Алексеевич

КЕГЭ-6 Четырех угольники (обычные, выпуклые)

Предположим, что есть задание типа 42612:

Черепахе был дан для исполнения следующий алгоритм:

Направо 135

Повтори 25 [Вперёд 250 Направо 90]

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

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

фигура есть квадрат со стороной 250, повернутый на 45 градусов
решать методом "подсчета точек" явно не стоит
рисовать сетку тоже смысла не имеет, но нарисуем оси
нарисуем чертеж и подумаем

Нарисуем задание на бумаге в клеточку и получим примерно следующее
Затем напишем программу от лица Черепашки и выведем координаты вершин A, B, C, D

import turtle
# Запусти меня

import turtle
tt = turtle.Pen()
tt.speed(10)
print('A =', tt.pos())
m = 1
tt.left(90) # поворот в сторону оси ординат (положительную)
tt.right(135)
tt.fd(250); tt.right(90); # проход по стороне AB 
print('B =', tt.pos())
tt.fd(250); tt.right(90); # проход по стороне BC 
print('C =', tt.pos())
tt.fd(250); tt.right(90); # проход по стороне CD 
print('D =', tt.pos())
for i in range(22): # проходы по условию (можно сократить или вообще не выполнять)
  tt.fd(250); tt.right(90);  
turtle.done()

Скопируем значения A,B,C. Нужны вещественные значения (точности должно хватить)

A = (0.00, 0.00)
B = (176.78, -176.78)
C = (0.00, -353.55)
D = (-176.78, -176.78)

Запишем их в комплексном представлении. Создадим пару подпрограмм

ksp(a, b, r=0) - возвращает скалярное произведение a на b при r=0 и векторое/косое произведение a на b в противном случае
angle(A, B, C, P) - возвращает 1 если точка P лежит строго внутри угла ABC (угол в геометрическом смысле, то есть меньше развернутого)
0 в противном случае (в том числе если угол нулевой или развернутый - эти углы нас пока не интересуют)

Решать будем исходя из того, что выпуклый четырехугольник есть "пересечение двух противоположных углов, которые меньше развернутого"
Надо понять, как определить, что точка P лежит внутри угла ABC (который меньше развернутого, то есть "геометрический угол")
Будем рассматривать прямые как ориентированные объекты (то есть направление прямой AB задается направлением от точки A к точке B)
Тогда \(P\in\angle ABС \) тогда и только тогда, когда

A, P лежат по одну сторону от BC
и C,P лежат по одну сторону от BA

Это нетрудно проверить с помощью векторного/косого произведений

def ksp(A,B, r=0): #вычисление косого (r !=0 ) и скалярного произведения (r = 0)
  if r == 0 : return A.real*B.real + A.imag*B.imag 
  return A.real*B.imag - A.imag*B.real
def angle(A, B, C, P):
  v11 = ksp(A - B, C - B, 1) # косое произведение вершин угла "друг на друга"
  v12 = ksp(P - B, C - B, 1)
  v21 = ksp(C - B, A - B, 1) # вообще-то равно -v11 (можно не считать)
  v22 = ksp(P - B, A - B, 1)
  if v11 * v12 > 0 and v21*v22 > 0 : return 1 # точка расположена строго в "геометрическом"углу ABC
  return 0 
A = complex(0.00, 0.00) # A, B, C, D - координаты вершин четырехугольника в комплексном предствлении
B = complex(176.78, -176.78)
C = complex(0.00, -353.55)
D = complex(-176.78, -176.78)
ans = 0 #инициализация количества внутренних точек
for x in range(-200, 200): # можно от min до max по x - взяли с запасом
  for y in range(-400, 50):# не долже "цеплять" точки вершин
    P = complex(x,y) # запись точки в комплексном формате
    rB = angle(A, B, C, P)  # проверка на принадлежность углу B строго внутри
    rD = angle(C, D, A, P)  # проверка на принадлежность углу D строго внутри
    if rB * rD == 0 : continue # не принадлежит двум углам одновременно
    ans += 1 #величение количества "внутренних точек"
print(f'{ans} {B=}')

Итак способ работает на четырех угольниках с поиском внутренних точек.
Попробуем адаптировать на случай с включение точек на границе
Рассмотрим задание типа 42569

Черепахе был дан для исполнения следующий алгоритм:

Повтори 16 [Налево 36 Вперёд 4 Налево 36]

Определите, сколько точек с целочисленными координатами будут находиться внутри области,

ограниченной линией, заданной данным алгоритмом. Точки на линии следует учитывать.

Размер фигуры небольшой, поэтому можно нарисовать рисунок с сеткой и "подсчитать руками".
Забудем про это и модифицируем решение по данную задачу
Вначале, как и ранее, нарисуем макет на бумаге и напишем программу от лица Черепашки
Координаты удобнее сразу выводить в комплексном предствалении (можно в строку через запятую)


import turtle
# Запусти меня

import turtle
tt = turtle.Pen()
tt.speed(10)
tt.left(90)
alf = 'ABCDE'
m = 1
for i in range (5):
  print(alf[i],'=', complex(tt.pos()))
  tt.left(36); tt.fd(4); tt.left(36); # проход по очередной стороне
for i in range(11): # проходы по условию (можно сократить или вообще не выполнять)
  tt.left(36); tt.fd(4); tt.left(36);  
turtle.done()

Вершин уже 5, поэтому заведем для них список.
Углы можно брать через один, но будем считать, что многоугольник есть пересечение всех углов
Надо проверять принадлежность стороне и совпадение с вершиной.
Напишем программу, проверки принадлежности точки интервалу (AB)
Совпадение будем проверять только с начальной точкой стороны (то есть для AB с вершиной A)
Координаты точек на сторонах будем выводить

Точка принадлежит интервалу (AB) если она принадлежит лучам AB и BA \(P \in \overrightarrow{AB}<=>\ когда\ векторное\ \overrightarrow{AP}\cdot\overrightarrow{AB} = 0,\\ а\ скалярное\ \overrightarrow{AP}\cdot\overrightarrow{AB} > 0 \)

Скопируем значения A,B,C,D,E в список в комплексном представлении
Для проверки принадлежности точки интервалу напишем подпрограмму interval(A,B,P)

def ksp(A,B, r=0): #вычисление косого (r !=0 ) и скалярного произведения (r = 0)
  if r == 0 : return A.real*B.real + A.imag*B.imag 
  return A.real*B.imag - A.imag*B.real
def angle(A, B, C, P):
  v11 = ksp(A - B, C - B, 1) # косое произведение вершин угла "друг на друга"
  v12 = ksp(P - B, C - B, 1)
  v21 = ksp(C - B, A - B, 1) # вообще-то равно -v11 (можно не считать)
  v22 = ksp(P - B, A - B, 1)
  if v11 * v12 > 0 and v21*v22 > 0 : return 1 # точка расположена строго в "геометрическом"углу ABC
  return 0 
def interval(A,B,P):
  v0 = ksp(P - A, B - A, 1) # косое произведение для проверки принадлежности прямой
  if v0 : return 0
  v1 = ksp(P - A, B - A) # 1 скалярное произведение
  v2 = ksp(P - B, A - B) # 2 скалярное произведение
  if v1 > 0 and v2 > 0 : return 1
  return 0
  
A = 0j
B = (-2.351141009169892+3.23606797749979j)
C = (-6.155367074350506+2.000000000000001j)
D = (-6.155367074350507-1.9999999999999991j)
E = (-2.351141009169893-3.23606797749979j)
V =(A,B,C,D,E)
kin, kg, kv = 0, 0, 0 #инициализация количества внутренних, граничных и вершинных точек
for x in range(-20, 20): # можно от min до max по x - взяли с запасом
  for y in range(-20, 20):# не долже "цеплять" точки вершин
    P = complex(x,y) # запись точки в комплексном формате
    r1 = 1
    for i in range(5):
      r1 *= angle(V[i], V[(i + 1) % 5], V[(i + 2) % 5], P)  # проверка на принадлежность очередному углу строго внутри
      r2 = interval(V[i], V[(i + 1) % 5], P)
      if r2 :
        print(f'gr: {x=} {y=} {i=}')
        kg += 1
      if P == V[i]  :
        print(f'vr: {x=} {y=} {i=}')
        kv += 1
    kin += r1
ans = kin + kg + kv
print(f'{ans=} {kin=} {kg=} {kv=}')

Подведем небольшой итог.
Для решения задач вычислительной геометрии с исполнителями типа Черепашка, Чертежник полезно

Хранить точки плоскости в "комплексном" представлении. Это "облегчает" действия с векторами
Для решения задач нужно уметь составлять подпрограммы
1. скалярного и векторного/косого произведения
2. проверки принадлежности точки прямой, лучу, отрезку/интервалу
3. проверки положения точки относительно ориентированной прямой
4. проверки принадлежности точки "геометрическому" углу
5. проверки вида "ориентированного" угла (меньше развернутого, больше развернутого, развернутый, нулевой)
6. получать уравнение прямой по точкам
7. находить точку пересечения прямых
Знать некоторые методы библиотеки cmath (polar, phase)
Полезно знать операции с комплексными числами и их геометрические свойства

Печать