|
|
Примечание. Это урок с задачами по информатике (раздел алгоритмы). Если Вам необходимо решить задачу по информатике, которой здесь нет - пишите об этом в форуме. Скорее всего ее решение дополнит данный курс с задачами по информатике.
Задача.
На плоскости даны два отрезка, заданные целочисленными координатами. Определить, есть ли у них общая точка пересечения.
Решение.
Для того, чтобы выяснить, пересекаются ли отрезки, составим уравнения прямых, которым принадлежат заданные отрезки. Если система уравнений для данных прямых имеет решение, то такие прямые имеют точку пересечения. Если точка пересечения находится между координатами точек, принадлежащих отрезкам, то отрезки пересекаются.
Обозначения:
Отрезок 1 обозначим как AB и пусть он имеет координаты A(x1;y1) B(x2; y2)
Отрезок 2 обозначим как CD и пусть он имеет координаты C(x3;y3) B(x4; y4)
Шаг 1. Ввод данных (x1;y1) (x2; y2) (x3;y3) (x4; y4)
Чтобы вычислить правильные угловые коэффициенты, должно выполняться условие x1 ≤ x2; x3 ≤ x4;
Если нет - то меняем местами пары координат отрезков.
Шаг 2. Если x1 ≥ x2 то меняем между собой значения x1 и x2 и y1 и y2
Шаг 3. Если x3 ≥ x4 то меняем между собой значения x3 и x4 и y3 и y4 ;
Шаг 4. Проверяем, равны ли между собой у2 и у1,
если у2 = у1 да, то принимаем k1 = 0 иначе
Определяем угловой коэффициент в уравнении прямой:
k1 = ( у2 - у1 ) / ( x2 - x1 )
Шаг 5. Проверяем, равны ли между собой у3 и у4,
если у3 = у4 да, то принимаем k2 = 0 иначе
Определяем угловой коэффициент в уравнении прямой:
k2 = ( у4 - у3 ) / ( x4 - x3 )
Шаг 6. Проверим отрезки на параллельность.
Если k1 = k2 , то прямые параллельны и отрезки пересекаться не могут. Решение задачи прекращаем.
Шаг 7. Вычисляем значения свободных переменных
Определяем свободные члены в уравнении прямой:
b1 = у1 - k1 * x1
b2 = у3 - k2 * x3
Шаг 8. Решаем систему уравнений:
y = k1 x + b1
y = k2 x + b2
Если прямые имеют точку пересечения, то
k1 x + b1 = k2 x + b2
Откуда и вычисляем точку пересечения прямых
x = ( b2 - b1 ) / ( k1 - k2 )
y = k1 x + b1.
Шаг 9.Учтем, что точка пересечения прямых может лежать вне отрезков, принадлежащих этим прямым. Таким образом, если отрезки пересекаются, то, поскольку
x1 ≤ x2; x3 ≤ x4;
должны выполняться условия:
x1 ≤ x4 и x4 ≤ x2
или
x1 ≤ x3 и x3 ≤ x2
Если одно из двух условий верно, то отрезки имеют точку пересечения, иначе - отрезки не пересекаются.
Виды алгоритмов. Види алгоритмiв |
Описание курса
|
