Задача 5. «Пересечение отрезков»

Здесь A¹ ,A¹ ,A² ,A² – константы, x ,y

– точки, принадлежащие

x y x y a a

отрезку, при t_a изменяющемся от 0 до 1. Аналогично для отрезка b:

x_b = B¹ + t_b (B² – B¹ )
x

x

x

y_b = B¹ + t_b (B² – B¹ )

y

y

y

Таким образом, приравнивая соответствующие координаты, полу- чаем задачу нахождения параметров t_a, t_b, при которых бы выполнялись равенства:

A¹ + t (A² – A¹ ) = B¹ + t (B² – B¹ )

24. 
    a x x x b x x
    

A¹ + t (A² – A¹ ) = B¹ + t (B² – B¹ )

24. 
    a y y y b y y
    

После разрешения системы относительно t_a,t_b получаем:

t_a (A¹ – A² ) + t (B² – B¹ ) = A¹ – B¹

x

x

b

x

x

x

x

t_a (A¹ – A² ) + t (B² – B¹ ) = A¹ – B¹

y

y

b

y

y

y

y

А это есть система из двух линейных уравнений относительно t_a, t_b.

Известно, что система: a₁ x + b₁ y = c₁

a₂ x + b₂ y = c₂

имеет следующее решение:

a₁ = A¹ b₁ = B² c₁ = A¹
x

x

x

a₂ = A¹ b₂ = B² c₂ = A¹

y

y

y

• 
  A²
  
• 
  B¹
  x
  
  
• 
  B¹
  x
  
  
• 
  A²
  y
  
  
• 
  B¹
  y
  
  
• 
  B¹
  y
  
  

откуда легко находится d,d_x,d_y. Если d отличен от нуля, то система име- ет единственное решение. Правда, следует помнить, что искомые t_a, t_b параметрически задают отрезки, только если они лежат в диапазоне [0,1], в противном случае – точка пересечения прямых, на которых ле- жат отрезки, находится вне этих самых отрезков.

Если d равен нулю, а хотя бы один из d_x,d_y отличен от нуля, то от- резки лежат на параллельных прямых, или, как говорят математики, они коллинеарны. Если же все три d,d_x,d_y равны нулю, то это значит, что от- резки лежат на одной и той же прямой, где опять возможны три слу- чая – либо отрезки не перекрываются, либо перекрываются в одной точ- ке, либо перекрываются в бесконечном множестве точек.

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

Одним из важных элементов комбинаторики являются переста- новки. Перестановки без повторений – комбинаторные соединения, которые могут отличаться друг от друга лишь порядком входящих в них элементов. Число таких перестановок определяется как n!.

Для числа 3 количество перестановок будет равно 3! = 3 * 2 * 1 = 6.

Для четырех: 4! = 4 * 3 * 2 * 1 = 24.

Часто для генерации перестановок используется алгоритм Дейкстры для получения всех перестановок по алфавиту. Разберем этот алгоритм.

Пусть у нас есть первая перестановка (например, 1234). Для нахо- ждения следующей перестановки выполняем три шага.

1. 
   Двигаясь с предпоследнего элемента перестановки, ищем эле- мент a[i], удовлетворяющий неравенству a[i] < a[i + 1]. Для перестанов- ки 1234, это число 3, т. к. (3 < 4).