Задача 6.
Определить, пересекается ли прямая ax+b=y и отрезок с концами (x1,y1), (x2,y2).
|
Решение задачи 6.
Вариант 1. Можно через концы отрезка провести прямую cx+d=y и определить, принадлежит ли точка пересечения двух прямых x, если она существует, отрезку. То есть, мы должны решить уравнение x*(c-a)=(b-d), найти y=ax+b, и проверить выполнение неравенств x1<=x<=x2, y1<=y<=y2.
Но при нахождении x при делении могут возникнуть большие вычислительные погрешности или даже переполнение или потеря значимости, в результате чего получится неверный ответ.
Вариант 2. Обозначим F(x,y)=ax+b-y. Прямая ax+b=y разбивает плоскость на три части: в одной F(x,y)>0, в другой F(x,y)<0 и на прямой ax+b=y F(x,y)=0 . Если эта прямая пересекает отрезок, то либо концы отрезка лежат в различных полуплоскостях, либо хотя бы одна концевая точка отрезка лежит на прямой. Это равносильно выполнению следующего неравенства F(x1,y1)*F(x2,y2)<=0. Таким образом, не вычисляя точку пересечения, мы по знаку функционала судим о том, имеют ли прямая и отрезок общую точку. Очевидно, что второй вариант решения подзадачи предпочтительнее первого.
|
