Геометрия: задачи с использованием геометрических понятий

Геометрия

При решении геометрических задач скалярное произведение векторов используется для определения угла (или косинуса угла) между векторами (для проверки перпендикулярности векторов, для определения наибольшего или наименьшего угла).

Векторное произведение двух векторов позволяет определить ориентацию одного объекта относительно другого (по одну сторону или по разные, внутри или снаружи), а также направление движения (влево или вправо, вниз или вверх, по часовой стрелке или против часовой).

Примеры задач

Задача 1. Мэрия решила выделить деньги на постройку кольцевой автодороги вокруг города. Координаты всех домов в городе заданы парой целых чисел на плоскости.

Уровень 1. Описать алгоритм построения дороги минимальной длины в виде отрезков, соединяющих точки-дома, вдоль которых должна пройти дорога при условии, что внутри дороги окажутся все остальные дома города.

Можно использовать алгоритм Джарвиса построения выпуклой оболочки:

Найти точку с минимальной координатой по оси $OX$. Запомнить ее.
Построить вектор, задающий первоначальное вертикальное направление (за начало вектора можно взять найденную точку).
В цикле перебирая все остальные точки, чтобы найти такую, чтобы вектор с концом в этой точке, а началом в исходной образовал с первоначальным вектором минимальный угол (минимальному углу соответствует максимальный косинус, который определяется из формулы скалярного произведения). Найденная таким образом точка будет точкой из выпуклой оболочки.
Найденную точку принять за исходную, новый построенный вектор принять за исходное направление и из оставшихся $N-2$ точек искать следующую точку по принципу, изложенному в предыдущем пункте.
Процесс прекратить, когда дойдем до первой выбранной точки или переберем по количеству $N$ точек (предотвращение зацикливания).

Уровень 2. Написать программу, которая выводит в файл координаты домов, вдоль которых должна пройти кольцевая автодорога.

Формат ввода:

Количество домов N (3<N<50000)

Координаты 1-го дома X₁ Y₁ (2 числа через пробел)

…

Координаты N-го дома X_N Y_N (2 числа через пробел)

Формат вывода:

Координаты 1-го дома X₁ Y₁ (2 числа через пробел)

…

Координаты K-го дома X_K Y_K (2 числа через пробел)

Пример:

Входные данные:                      Выходные данные:

5                                                  1 1

1 1                                               2 3

2 3                                               4 4

3 2                                               4 1

4 4

4 1

Программа 1.1 (на языке QBasic):

OPEN “INPUT.TXT” FOR INPUT AS #1

OPEN “OUTPUT.TXT” FOR OUTPUT AS #2

INPUT #1, n

DIM x(1 TO n), y(1 TO n)                      ' координаты n точек

FOR i = 1 TO n

INPUT #1, x(i), y(i)

NEXT

' поиск точки с минимальной координатой x

' n1- номер найденной точки; x1,y1- координаты найденной точки

x1 = x(1): y1 = y(1): i1 = 1: n1 = 1

PRINT #2, x1, y1

FOR i = 2 TO n

IF x(i) < x1 THEN x1 = x(i): y1 = y(i): i1 = i: n1 = i

NEXT

X0 = X1: y0 = Y1 – 1                                ' взяли вспомогательную точку (x0, y0)

k = 0

DO

mcos = -2                    ‘ число, необходимое для поиска максимального cos,

‘ т.е. минимального угла

X10 = X1 - X0: Y10 = Y1 - Y0                        ' строим вектор а

a = SQR(X10 ^ 2 + Y10 ^ 2)            ' находим |a|

FOR i = 1 TO n

IF i <> i1 THEN

xi1 = x(i) - x1: yi1 = y(i) - y1                ' вектор b

b = SQR(xi1 ^ 2 + yi1 ^ 2)                   ' |b|

cosa = (X10 * xi1 + Y10 * yi1) / (a * b)        ' cos угла из скалярного

‘ произведения

IF cosa > mcos THEN mcos = cosa: nomi = i

END IF

NEXT i

k = k + 1

IF nomi = n1 THEN END

x0 = x1: y0 = y1                                          ' за вектор а берем b

x1 = x(nomi): y1 = y(nomi)

PRINT #2, x1, y1

i1 = nomi

LOOP UNTIL k > n – 1

Уровень 3. Смоделировать на экране монитора решение задачи, изобразив каждый из домов в виде точки или окружности малого радиуса. Изобразить построение кольцевой автодороги минимальной длины в виде замкнутой ломаной. Возможно использование для задания экранных координат точек датчика случайных чисел. Исследовать процесс построения выпуклой оболочки при малом и большом количестве точек. Сравнить процесс построения двумя разными алгоритмами (Джарвиса и Грэхема).

Программа 1.3 (на языке QBasic):

SCREEN 9                                  ‘программа с графическим оформлением

INPUT "Количество точек - ", n

RANDOMIZE TIMER

DIM x(1 TO n), y(1 TO n)

FOR i = 1 TO n

x(i) = INT(RND * 600 + 20)

y(i) = INT(RND * 300 + 20)

CIRCLE (x(i), y(i)), 3

NEXT

IF n = 1 THEN END

x1 = x(1): y1 = y(1): i1 = 1: n1 = 1

FOR i = 2 TO n

IF x(i) < x1 THEN x1 = x(i): y1 = y(i): i1 = i: n1 = i

NEXT

x0 = x1: y0 = y1 – 1

k = 0

DO

mcos = -2

x10 = x1 - x0: y10 = y1 - y0

a = SQR(x10 ^ 2 + y10 ^ 2)

FOR i = 1 TO n

IF i <> i1 THEN

xi1 = x(i) - x1: yi1 = y(i) - y1

b = SQR(xi1 ^ 2 + yi1 ^ 2)

cosa = (x10 * xi1 + y10 * yi1) / (a * b)

IF cosa > mcos THEN mcos = cosa: nomi = i

END IF

NEXT i

LINE (x1, y1)-(x(nomi), y(nomi))

k = k + 1

IF nomi = n1 THEN END

x0 = x1: y0 = y1

x1 = x(nomi): y1 = y(nomi)

i1 = nomi

LOOP UNTIL k > n – 1

Задача 2. «Штраф за левые повороты». Новый градоначальник города Глупова решил с целью пополнения бюджета и экономии горючего провести кампанию борьбы с “левым” уклоном. Для этого он запретил водителям выполнять левые повороты, установив за каждый поворот налево штраф в 1 млн. рублей (прейскурант 1994 года). От тяжелого прошлого Глупову достались улицы, которые могут пересекаться под любыми углами. Градоначальник приказал установить компьютерную систему слежки за автомобилями, которая фиксирует координаты каждого автомобиля в начале движения, в конце движения и во время поворота.

Уровень 1. Описать алгоритм вычисления штрафа водителю автомобиля, если задана последовательность координат движения этого автомобиля.

Поворот считается левым, если направление текущего отрезка траектории a2 относительно направления предыдущего отрезка a1 меняется по наименьшему углу в левую сторону (поворот против часовой стрелки). А это означает, что векторное произведение векторов [a1 × a2] > 0 (по правилу «буравчика»).

1.      Из координат первых трех точек в заданной последовательности определить два вектора a1 и a2.

2.      Составить их векторное произведение.

3.      Если [a1 × a2] > 0, то увеличить счетчик для подсчета левых поворотов на 1.

4.      Переопределить данные, взяв за вектор a1 вектор a2.

5.      Определить вектор a2, взяв координаты следующей точки в последовательности.

6.      Повторить процесс с пункта 2.

7.      После перебора всех точек значение счетчика будет содержать ответ задачи.

Уровень 2. Написать программу, вычисляющую штраф водителю автомобиля, если задана последовательность координат движения этого автомобиля.

Формат ввода:

Координаты начала движения X₀ Y₀ (2 числа через пробел)

Координаты первого поворота X₁ Y₁ (2 числа через пробел)

…

Координаты N-го поворота X_N Y_N (2 числа через пробел)

Координаты конца движения X_N+1 Y_N₊₁ (2 числа через пробел)

Формат вывода:

Величина штрафа

Пример:

Входные данные:                 Выходные данные:

-2 -1                                        2 млн. руб.

2 0

-2 2

2 2

2 3

Рис. 7

Программа 2.1 (на языке QBasic):

OPEN “INPUT.TXT” FOR INPUT AS #1

OPEN “OUTPUT.TXT” FOR OUTPUT AS #2

DIM x(1 TO 1000), y(1 TO 1000)

n = 0

DO WHILE NOT (EOF(1))

n = n+1

INPUT #1, x(i), y(i)

LOOP

s = 0

a1 = x(1): b1 = y(1)

a2 = x(2): b2 = y(2)

FOR i = 3 TO n

a3 = x(i): b3 = y(i)

IF (a2 - a1) * (b3 - b2) - (b2 - b1) * (a3 - a2) > 0 THEN s = s + 1

a1 = a2: b1 = b2

a2 = a3: b2 = b3

NEXT i

PRINT #2, s; " млн. руб."

Уровень 3. Смоделировать на экране монитора решение задачи, изобразив траекторию движения автомобиля как ломаную, состоящую из направленных отрезков (векторов). Для наглядности можно изобразить оси координат. Выполнить масштабирование для любых вещественных значений координат.

На рисунке 7 показан пример иллюстрации к вышеуказанным входным данным - получается 2 левых поворота.

Примечание: При оформлении к задаче графического сопровождения не забывать, что экранная система координат является неправильной (левой), поэтому проверка векторного произведения на знак должна измениться, то есть значение должно быть < 0.

Программа 2.2 (на языке QBasic):

SCREEN 9

INPUT "N=", n

DIM x(1 TO n), y(1 TO n)

FOR i = 1 TO n

PRINT i; ": x,y "; : INPUT "", x(i), y(i)

NEXT i

minx = x(1): miny = y(1): maxx = x(1): maxy = y(1)

nminx = 1: nminy = 1: nmaxx = 1: nmaxy = 1

FOR i = 1 TO n

   IF x(i) < minx THEN

      minx = x(i): nminx = i

   ELSE

     IF maxx < x(i) THEN maxx = x(i): nmaxx = i

   END IF

   IF y(i) < miny THEN

      miny = y(i): nminy = i

   ELSE IF maxy < y(i) THEN maxy = y(i): nmaxy = i

   END IF

NEXT i

VIEW (200, 100)-(620, 330), 3, 7

dx = (maxx - minx) / 10

dy = (maxy - miny) / 10

WINDOW (minx - dx, miny - dy)-(maxx + dx, maxy + dy)

   CIRCLE (x(1), y(1)), (dx + dy) / 20, 0

   PAINT (x(1), y(1)), 4, 0

FOR i = 2 TO n

   CIRCLE (x(i), y(i)), (dx + dy) / 30, 0

   PAINT (x(i), y(i)), 0, 0

NEXT

s = 0

a1 = x(1): b1 = y(1)

a2 = x(2): b2 = y(2)

LINE (a1, b1)-(a2, b2)

FOR i = 3 TO n

a3 = x(i): b3 = y(i)

LINE (a3, b3)-(a2, b2)

IF (a2 - a1) * (b3 - b2) - (b2 - b1) * (a3 - a2) > 0 THEN s = s + 1

a1 = a2: b1 = b2

a2 = a3: b2 = b3

NEXT i

LOCATE 23

PRINT "Штраф: "; s; " млн."

Задача 3. Произвольный N-угольник задан декартовыми координатами своих вершин на плоскости и на этой же плоскости дана произвольная точка.

Уровень 1. Описать алгоритм, который определяет, попадает ли точка внутрь многоугольника.

1.     Взять координаты двух вершин, лежащих на первой стороне многоугольника, и построить два вектора с началом в заданной точке и концами в этих вершинах.

2.      Из формулы скалярного произведения определить косинус угла, образованного векторами.

3.     Используя формулу арккосинуса, вычислить угол и прибавить его к значению переменной для суммарного угла (предварительно вычисляем векторное произведение векторов, чтобы определить знак угла).

4.      Повторить процесс со 2-го пункта для каждой пары вершин других сторон многоугольника.

5.      Полученную величину суммарного угла сравнить с нулем и 2π.

6.      Если угол равен нулю, то точка находится снаружи, а если – 2π, то внутри.

Уровень 2. Написать программу, которая определяет, попадает ли точка внутрь N- угольника.

Формат ввода:

Количество вершин многоугольника (число N)

Координаты первой вершины X₁ Y₁ (2 числа через пробел)

…

Координаты N-й вершины X_N Y_N (2 числа через пробел)

Координаты точки X_a Y_a (2 числа через пробел)

Формат вывода:

Слово «IN» (если точка внутри) или слово «OUT» (если точка снаружи)

Пример:

Рис. 8

Входные данные:                      Выходные данные:

5                                                  OUT

-2 0

0 2

0 0

2 0

0 -3

1 1

Программа 3.1 (на языке QBasic):

DECLARE FUNCTION acos! (X!)

PRINT "          CОДЕРЖИТСЯ ЛИ ТОЧКА ВНУТРИ N-УГОЛЬНИКА"

INPUT "N=", n

DIM x(1 TO n), y(1 TO n)

PRINT "Введите координаты вершин многоугольника"

FOR i = 1 TO n

PRINT i; ": x,y "; : INPUT "", x(i), y(i)

NEXT i

INPUT "Введите координаты точки ", ax, ay

s = 0                                                                                ' Суммарный угол

FOR i = 1 TO n - 1

a1 = x(i) - ax: b1 = y(i) - ay

a2 = x(i + 1) - ax: b2 = y(i + 1) - ay

u1 = a1 * b2 - b1 * a2                                                  'Векторное произведение

u2 = SQR(a1 ^ 2 + b1 ^ 2) * SQR(a2 ^ 2 + b2 ^ 2)   'Произведение модулей

u3 = a1 * a2 + b1 * b2                                                 'Скалярное произведение

IF u2 <> 0 THEN ugol = acos(u3 / u2)

IF u1 > 0 THEN s = s + ugol ELSE s = s - ugol

NEXT i

a1 = x(n) - ax: b1 = y(n) – ay                              'Последняя сторона многоугольника

a2 = x(1) - ax: b2 = y(1) - ay

u1 = a1 * b2 - b1 * a2

u2 = SQR(a1 ^ 2 + b1 ^ 2) * SQR(a2 ^ 2 + b2 ^ 2)

u3 = a1 * a2 + b1 * b2

IF u2 <> 0 THEN ugol = acos(u3 / u2)

IF u1 > 0 THEN s = s + ugol ELSE s = s - ugol

IF ABS(s) > 3.14 THEN PRINT "IN" ELSE PRINT "OUT"

FUNCTION acos (x)

' Функция арккосинуса

pi = 3.1415926#

IF ABS(x) >= .9999 THEN acos = 0 ELSE acos = pi / 2 - ATN(x / SQR(1! - x * x))

END FUNCTION

Программа 3.2 (на языке Pascal):
```
Type mas=array[1..100] of real;
Var
  i,n:Byte;
  xp,yp:Real;
  Angle,a,b,s:Real;
  x,y: mas;

function Len(x1,y1,x2,y2:Real):Real;
begin
  Len:=Sqrt(Sqr(x2- x1)+Sqr(y2-y1));
end;

function Vector(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2:Real):Real;
begin
  Vector:=(Ax2-Ax1)*(By2- By1)-(Bx2-Bx1)*(Ay2-Ay1);
end;

Function Scalar(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2:Real):Real;
begin
  Scalar:=(Ax2-Ax1)*(Bx2- Bx1)+(Ay2-Ay1)*(By2-By1);
end;

Function ArcCos(x:Real):Real;
Begin
  If Abs(x)>=0.9999 Then ArcCos:=0 Else ArcCos:=Pi/2-ArcTan(x/Sqrt(1- Sqr(x)));
End;

begin
  Write('Введите N: '); Readln(n);
  for i:=1 to n do begin
    Write('Введите x, y c #',i, ' ');
    Readln(x[i],y[i]);
  end;
  Write('Введите xp, yp '); Readln(xp, yp);
  Angle:=0;
  x[n+1]:=x[1]; y[n+1]:=y[1];
  for i:=1 to n do begin
    a:=Len(x[ i ],y[ i ],xp,yp);
    b:=Len(x[i+1],y[i+1],xp,yp);
    if (a<>0) And (b<>0) Then Begin
      s:=Scalar(xp,yp,x[i],y[i],xp,yp,x[i+1],y[i+1]);
      If Vector(xp,yp,x[i],y[i],xp,yp,x[i+1],y[i+1])>0 Then
        Angle:=Angle- ArcCos(s/(a*b))
      Else
        Angle:=Angle+ArcCos(s/(a*b));
    end;
  end;
  If Abs(Angle)>Pi Then Writeln('IN') Else Writeln('OUT');
  Readln;
end.
```
На рисунке 8 показан пример иллюстрации к вышеуказанным входным данным – в данном случае точка находится снаружи. Если, например, задать координаты точки
(-1; -1), то программа должна определить, что эта точка находится внутри.

4.4.2. Задачи для самостоятельного решения.

Задача 4. (Областная олимпиада, 1995).

Уровень 2. Написать программу, которая определяет выпуклый многоугольник с вершинами, принадлежащими множеству точек с координатами (x_i , y_i), где i = 1, 2, ..., n. Данный многоугольник содержит все точки указанного множества.

Указание. Эта задача аналогична задаче 1. Отличием является лишь то, что из множества вершин построенного выпуклого многоугольника необходимо исключить «лишние» точки, то есть те, которые лежат на сторонах многоугольника.

Формат ввода:

Количество точек (число N)

Координаты первой точки X₁ Y₁ (2 числа через пробел)

…

Координаты N-й точки X_N Y_N (2 числа через пробел)

Формат вывода:

Координаты первой вершины многоугольника X₁ Y₁ (2 числа через пробел)

…

Координаты K-й вершины многоугольника X_K Y_K (2 числа через пробел)

Задача 5. «Бассейн». (Районная олимпиада, 2000). Емкость для декоративного бассейна по предложению архитектора было решено выполнить в виде произвольной N-угольной призмы. Для того чтобы определить количество машин с грузоподъемностью G для вывоза земли, необходимо вычислить объем строящегося бассейна.

Уровень 2. Напишите программу, вычисляющую объем бассейна, если известна его высота H, а многоугольник в основании призмы задается Х, Y координатами своих вершин.

Формат ввода:

Высота бассейна H и грузоподъемность машины G (два числа через пробел)

Координаты первой вершины X₁ Y₁ (2 числа через пробел)

…

Координаты N-й вершины X_N Y_N (2 числа через пробел)

Формат вывода:

Вещественное число с 3 знаками после запятой (объем бассейна)

Целое число (количество машин)

Задача 6. (Областная олимпиада, 1997). Четыре населенных пункта a,b,c,D задаются декартовыми координатами на плоскости. Известно, что между пунктами прокладывают автотрассу.

Уровень 2. Определить, возникает ли необходимость в установлении светофора на перекрестке. Написать соответствующую программу.

Указание: Задача на определение пересечения двух прямых или двух отрезков.

Формат ввода:

Координаты X₁ Y₁пункта А (2 числа через пробел)

Координаты X₂ Y₂пункта b (2 числа через пробел)

Координаты X₃ Y₃пункта C (2 числа через пробел)

Координаты X₄ Y₄ пункта D (2 числа через пробел)

Формат вывода:

Слово «YES», если возникает необходимость в светофоре, слово «NO», если нет.

Задача 7. (Районная олимпиада, 1997). На декартовой плоскости задано N точек и M отрезков (отрезки между собой не пересекаются, параллельны оси ординат, и ни одна из множества N точек не лежит на отрезках).

Уровень 2. Соединить точки ломаной, не пересекающей отрезки во внутренних точках. Отобразить графически одно из возможных решений. Числа N, M, а также координаты точек и координаты концов отрезков вводятся с клавиатуры.

Формат ввода:

N и M (2 числа через пробел)

Координаты X₁ Y₁первой точки (2 числа через пробел)

…

Координаты X_N Y_NN-й точки (2 числа через пробел)

Координаты X_N₊₁ Y_N₊₁начала первого отрезка (2 числа через пробел)

Координаты X_N₊₂ Y_N₊₂конца первого отрезка (2 числа через пробел)

…

Координаты X_N₊₂_M-1 Y_N₊₂_M-1 начала M-го отрезка (2 числа через пробел)

Координаты X_N₊₂_M Y_N₊₂_M конца M-го отрезка (2 числа через пробел)

Формат вывода:

Рисунок на экране монитора

Уровень 3. Исследовать все возможные решения данной задачи. Определить длину кратчайшей ломаной.

Задача 8. (Областная олимпиада, 2001).

Уровень 2. Определить центр окружности минимального радиуса, содержащей все заданные точки на плоскости.

Указание: Искомая окружность может опираться либо на три точки, либо на две точки, лежащие на ее диаметре. Следовательно, надо перебрать все варианты троек и пар точек и среди окружностей, определяемых этими наборами точек, найти искомую. Можно ограничить перебор лишь точками, входящими в выпуклую оболочку, построение которой приведено в задаче 1.

Формат ввода:

N (число точек)

Координаты X₁ Y₁первой точки (2 числа через пробел)

…

Координаты X_N Y_NN-й точки (2 числа через пробел)

Формат вывода:

X Y R (координаты центра и радиус окружности через пробел)

Геометрия: задачи с использованием геометрических понятий

Примеры задач

4.4.2. Задачи для самостоятельного решения.