Примітка. Це урок з завданнями з інформатики (розділ алгоритми). Якщо Вам необхідно вирішити задачу з інформатики, якої тут немає - пишіть про це в форумі. Швидше за все її рішення доповнить даний курс з завданнями з інформатики.
Завдання.
На площині дано два відрізки, задані цілочисельними координатами. Визначити, чи є у них спільна точка перетину.
Рішення.
Для того, щоб з'ясувати, чи перетинаються відрізки, складемо рівняння прямих, яким належать задані відрізки. Якщо система рівнянь для даних прямих має рішення, то такі прямі мають точку перетину. Якщо точка перетину знаходиться між координатами точок, що належать відрізкам, то відрізки перетинаються.
Позначення.
Відрізок 1 позначимо як AB і нехай він має координати A (x1; y1) B (x2; y2)
Відрізок 2 позначимо як CD і нехай він має координати C (x3; y3) B (x4; y4)
Щоб обчислити правильні кутові коефіцієнти, повинна виконуватися умова x1 ≤ x2; x3 ≤ x4;
Якщо немає - то міняємо місцями пари координат відрізків.
Крок 6. Перевіримо відрізки на паралельність.
Якщо k1 = k2. то прямі паралельні і відрізки перетинатися не можуть. Рішення завдання припиняємо.
Якщо прямі мають точку перетину, то
k1 x + b1 = k2 x + b2
Крок 9 .Учтем, що точка перетину прямих може лежати поза відрізків, що належать цим прямим. Таким чином, якщо відрізки перетинаються, то, оскільки
x1 ≤ x2; x3 ≤ x4;
повинні виконуватися умови:
x1 ≤ x4 і x4 ≤ x2
або
x1 ≤ x3 і x3 ≤ x2
Якщо одне з двох умов вірно, то відрізки мають точку перетину, інакше - відрізки не перетинаються.