Задача. Общая точка
Два отрезка на плоскости заданы координатами своих концов. Определить имеют ли эти отрезки общие точки.
Замечание. Необходимо рассмотреть различные случаи взаимной ориентации отрезков: на одной прямой, на параллельных или пересекающихся прямых. Тестирование должно предусмотреть все такие ситуации.
Входные данные
Координаты концов двух отрезков [latex]AB, CD [/latex] в формате [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex] ([latex]x_i, y_i[/latex] — действительные числа).
Выходные данные
Расположение отрезков, а именно:
- «Intersect at point [latex](x, y)[/latex]»
- «Don’t intersect»
- «Paralell»
- «On the same line, but don’t intersect»
- «Overlap» (Находятся на одной прямой и хотя бы одна из точек совпадает)
Тесты
| Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex] | Расположение отрезков |
| 1 1 5 4 1 3 5 3 | Intersect at point (3.66667, 3) |
| -7 2 -4 2 -6 3 -3 3 | Paralell |
| 1 2 3 2 2 2 6 2 | Overlap |
| 1 2 4 2 5 2 7 2 | On the same line, but don’t intersect |
| 1 2 4 4 2 1 5 3 | Paralell |
| 1 1 4 2 7 3 10 4 | On the same line, but don’t intersect |
| 1 1 5 3 5 3 7 4 | Overlap |
| 1 1 5 4 1 4 5 2 | Intersect at point (3.4, 2.8) |
| 1 1 2 4 3 2 6 4 | Don’t intersect |
| Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex] | Расположение отрезков |
| 1 1 1 5 3 2 3 4 | Paralell |
| 1 2 4 5 2 2 2 5 | Intersect at point (2, 3) |
| 2 1 2 2 2 4 2 6 | On the same line, but don’t intersect |
| 2 1 2 5 1 2 4 2 | Intersect at point (2, 2) |
| 1 2 4 2 2 3 2 5 | Don’t intersect |
Алгоритм решения
Представленный в данной программе алгоритм достаточно объемный и содержит в себе большое количество вариантов поведения программы, поэтому разбирать его будем постепенно.
Начнем с функций, которые понадобятся в дальнейшем ходе решения:
- areCollinear — функция, принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.
( Основная формула: [latex]\frac{x_1}{x_2}[/latex] [latex]=[/latex] [latex]\frac{y_1}{y_2}[/latex] ) - getMin — возвращает минимум двух чисел.
- getMax — возвращает максимум двух чисел.
- projectionsIntersect — функция, принимающая абсциссы или ординаты двух векторов и возвращающая логическое значение true, если проекции отрезков на соответствующую ось пересекаются, и false в противном случае.
- getSlope — функция, принимающая координаты отрезка и возвращающая угол наклона прямой, на которой он расположен.
( Основная формула: [latex]\frac{y_2 — y_1}{x_2 — x_1}[/latex] ) - getYIntercept — функция, принимающая координаты отрезка и возвращающая свободный член уравнения прямой, на которой он расположен.
( Основная формула: [latex]\frac{x_2y_1 — x_1y_2}{x_2 — x_1}[/latex] ) - getCos — функция, принимающая координаты двух векторов и возвращающая косинус угла между ними.
( Основная формула: [latex]\frac{x_1x_2 + y_1y_2}{\sqrt(x_1^2 + y_1^2) + \sqrt(x_2^2 + y_2^2)}[/latex] )
Перейдем к основной части программы. Сразу следует оговорить, что последующее решение будет базироваться на векторах и работе с уравнением прямой вида [latex] y = kx + b [/latex], поэтому для удобства отдельно заведем переменные для координат векторов соответствующих отрезкам и значений вычисленных коэффициентов и свободных членов уравнений прямых. Одной из главных проблем на пути решения стали отрезки располагающиеся на прямых вида [latex]x = a [/latex], ведь если обратится к пунктам 5, 6 можно заметить, что в таких случаях мы получим исключение из-за деления на ноль. Этим вызвано вынужденное разделение программы на два блока — где ни один из отрезков не располагается параллельно оси ординат и когда хотя бы один из них параллелен. Это удается достичь благодаря инициализации логических переменных, принимающих значение true, когда отрезок расположен на прямой [latex]x = a[/latex]. Также изначально подсчитываем значения переменных yIntercept1, yIntercept2, slope1, slope2 тогда, когда это возможно, так как они будут задействованы в дальнейшем.
Теперь мы можем приступить к общему рассмотрению сложившейся ситуации, когда прямые параллельные оси ординат отсутствуют:
- Решим систему уравнений для двух заданных прямых и таким образом найдем точку их пересечения.
[latex] \left\{\begin{matrix}
k_1x + b_1 = y & \\
k_2x + b_2 = y &
\end{matrix}\right.[/latex] - Найдя точку с координатами [latex](xIntersection,yIntersection)[/latex], следующим шагом станет проверка : принадлежит ли найденная точка имеющимся отрезкам. Для этого воспользуемся формулой скалярного произведения и определим косинус угла между векторами с началом в точке [latex](xIntersection, yIntersection)[/latex] и концами в соответствующих концах отрезка. Выполняем ее для двух отрезков. Если в обоих случаях найденный косинус будет [latex] \le[/latex] [latex]0[/latex], то точка находится на двух отрезках одновременно и является их пересечением. Выводим сообщение «Intersect at point [latex](xIntersection, yIntersection)[/latex]«.
- В случае, если такая точка не найдена в следствие определенных причин, рассмотрим следующие возможные ситуации:
а) При условии, что равны свободные члены уравнения прямых и точка не была найдена, можем проверить утверждение, что рассматриваемые прямые совпадают, а заданные отрезки находятся на ней. Здесь требуют рассмотрения два варианта: отрезки накладываются, если проекции отрезков на ось абсцисс накладываются друг на друга, или же отрезки находятся на одной прямой и не пересекаются. Выводим соответствующее сообщение : «Overlap»/»On the same line, but don’t intersect».
б) Если свободные члены не равны и не выполнилось ни одно из предыдущих утверждений, приходим к выводу, что возможно отрезки, которые задают вектора, параллельны. Выполняем проверку на коллинеарность , в случае подтверждения предположения выводим сообщение : «Parallel».
в) Пройдя через все вышеупомянутые проверки и не получив логического значения true, определяем, что данные отрезки не пересекаются и не удовлетворяют ни одному из особенных случаев. Выводим сообщение : «Don’t intersect».Таким образом рассмотрение общего случая окончено. Перейдем ко второй ситуации:
- Если оба отрезка расположены на прямых вида [latex]x = a[/latex], то имеем следующие варианты:
а) Если отрезки расположены на одной прямой и их проекции на ось ординат пересекаются, выводим сообщение : «Overlap».
б) Если отрезки расположены на одной прямой и их проекции на ось ординат не пересекаются, выводим сообщение : «On the same line, but don’t intersect».
в) Если отрезки расположены не на одной прямой, выводим сообщение «Paralell».
- При условии, что только одна из прямых имеет вид [latex]x = a[/latex], рассмотрим следующие ситуации:
а)Только одна из прямых имеет вид [latex]x = a[/latex] и обе имеют коэффициент угла наклона равный [latex]0[/latex]. Перед нами две прямые вида: [latex] y = b[/latex] и [latex]x = a [/latex]. Выполняем смену между соответствующими координатами, чтобы не дублировать код для двух аналогичных ситуаций и рассматриваем только одну из них. Нетрудно заметить, что единственным решением является точка [latex](x_3/x_4, y_1/y_2)[/latex] . Используя метод getCos, выполняем уже описанную выше проверку на принадлежность точки отрезку. Если да — выводим сообщение : «Intersect at point [latex](x_3, y_1)[/latex]», в противном случае : «Don’t intersect».
б) Однако, ни одна из предыдущих проверок могла не выполниться, так как существует еще одно расположение отрезков на прямых [latex] y = kx + b [/latex] и [latex]x = a [/latex]. Выполняем аналогичную операцию по смене координат во избежание дублирования кода. Единственным решением данной системы может являться точка [latex](x3/x4 + yIntercept1, x3/x4)[/latex]. Повторяем операции аналогичные последним из пункта б). Выводим сообщение: «Intersect at point [latex](x3 + yIntercept1, x3)[/latex]» или «Don’t intersect».
(В последних двух пунктах несколько раз координаты были записаны через черту, что , вероятно, требует пояснения: в этих ситуациях наблюдалось равенство и какую координату мы выберем не существенно).
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include <iostream> #include <math.h> using namespace std; bool areCollinear(double x1, double y1, double x2, double y2) { return x1 / x2 == y1 / y2 ? true : false;// проверка на коллинеарность } double getMin(double x1, double x2) { return x1 < x2 ? x1 : x2; } double getMax(double x1, double x2) { return x1 > x2 ? x1 : x2; } // Проверка на пересечение проекций на оси, посредством нахождения взаимного расположения концов проекций bool projectionsIntersect(double x1, double x2, double x3, double x4) { return ((getMin(x1, x2) <= getMin(x3, x4) && getMin(x3, x4) <= getMax(x1, x2)) || ((getMin(x3, x4) <= getMin(x1, x2) && getMin(x1, x2) <= getMax(x3,x4)))); } // Вычисление коэффициента угла наклона уравнения прямой double getSlope(double x1, double y1, double x2, double y2) { return (y2 - y1) / (x2 - x1); } // Вычисление свободного члена уравнения прямой double getYIntercept(double x1, double y1, double x2, double y2) { return (x2 * y1 - x1 * y2) / (x2 - x1); } // Нахождение косинуса угла между векторами double getCos(double x1, double y1, double x2, double y2) { return (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) + sqrt(x2 * x2 + y2 * y2)); } int main() { double slope1, slope2; // Коэффициенты углов наклона уравнений прямых, на которых расположены отрезки bool f1 = false, f2 = false; // Логические флаги для прямых вида x = a double yIntercept1, yIntercept2; // Свободные члены уравнений прямых, на которых расположены отрезки double xIntersection, yIntersection; // Координаты точки пересечения, если она существует double x1, y1, x2, y2, x3, y3, x4, y4; // Заданные координаты концов отрезков cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4; double vx1 = x2 - x1; double vy1 = y2 - y1; // Вычислим координаты векторов, double vx2 = x4 - x3; // Задаваемых данными отрезками double vy2 = y4 - y3; slope1 = (vx1 != 0 ? getSlope(x1, y1, x2, y2) : 0); // Для прямых вида x = a slope2 = (vx2 != 0 ? getSlope(x3, y3, x4, y4) : 0); // Присваиваем значение 0 коэффициенту угла наклона vx1 != 0 ? yIntercept1 = getYIntercept(x1, y1, x2, y2) : f1 = true; // Для прямых вида x = a vx2 != 0 ? yIntercept2 = getYIntercept(x3, y3, x4, y4) : f2 = true; // Присваиваем флагу значение true if (!f1 && !f2) { xIntersection = (yIntercept2 - yIntercept1) / (slope1 - slope2); // Находим решение системы уравнений yIntersection = slope1 * xIntersection + yIntercept1; if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) // Проверяем находится ли точка на обоих отрезках cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")"; else if (yIntercept1 == yIntercept2) { if (projectionsIntersect(x1, x2, x3, x4)) cout << "Overlap"; else cout << "On the same line, but don't intersect"; } else if (yIntercept1 != yIntercept2 && (areCollinear(vx1, vy1, vx2, vy2) || (y1 == y2 && y3 == y4))) cout << "Paralell"; else cout << "Don't intersect"; } // Блок нахождения расположения для всех отрезков, кроме тех, где хотя бы один из них расположен на прямой вида x = a else { if (slope1 == 0 && slope2 == 0 && f1 && f2) { if (x1 == x4 && projectionsIntersect(y1, y2, y3, y4)) cout << "Overlap"; else if (x1 != x4) cout << "Paralell"; else cout << "On the same line, but don't intersect"; } // Блок для двух прямых вида x = a else if (f1 ^ f2 && slope1 == 0 && slope2 == 0) { if (f1) { swap(x1, x3); swap(x2, x4); swap(y1, y3); swap(y2, y4); swap(yIntercept1, yIntercept2); } yIntersection = y1; xIntersection = x3; if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")"; else cout << "Don't intersect"; } // Блок для прямых вида y = b и x = a else if (slope1 == 0 ^ slope2 == 0) { if (slope1 == 0) { swap(x1, x3); swap(x2, x4); swap(y1, y3); swap(y2, y4); swap(yIntercept1, yIntercept2); } xIntersection = x3; yIntersection = x3 + yIntercept1; if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")"; else cout << "Don't intersect"; } // Блок нахождения расположения, когда только одна пряма имеет вид x = a, а вторая y = kx +b } // Блок нахождения расположения, если хотя бы один отрезок находится на прямой вида x = a return 0; } |
Аналогичная задача на сайте e-olymp:
839. Пересечение отрезков (Засчитанное решение)
Проверил здесь. Проходит только 71%. Возможно я что-то не так переделал. Проверьте, пожалуйста. Возможно что-то не так со случаем на одной прямой?
Кстати, задача популярная. Например здесь есть решение. Но Вы своё доделайте.
Спасибо большое. Посмотрела пример решения. Он действительно лаконичнее и логичнее. Впредь попытаюсь находить более оптимальные варианты.
Однако, не понимаю, что не так с данным. Заменила все частные случаи на ответы «Yes» и «No» в соответствии с выходными данными предоставленной вами задачи. Зачтено на 100%.
Отлично, зачтено.
Видимо я где-то пропустил замену и у меня не прошла.
Сделайте, пожалуйста, где-нибудь в конце ссылки на похожие задачи с e-olymp №839 и №1615.
P.S. «более оптимальные» — так не следует говорить. Прилагательное «оптимальный» не имеет сравнительных степеней. Оно означает «наиболее приемлемый», «наилучший». А в математических текстах почти синонимично слову «экстремум». У вас будет даже целый курс методов оптимизации, где вы будете решать разнообразные задачи на поиск экстремума (оптимизационные задачи).