Ю2.15

Задача.  Общая точка

Два отрезка на плоскости заданы координатами своих концов. Определить имеют ли эти отрезки общие точки.

Замечание. Необходимо рассмотреть различные случаи взаимной ориентации отрезков: на одной прямой, на параллельных или пересекающихся прямых. Тестирование должно предусмотреть все такие ситуации.

Входные данные

Координаты концов двух отрезков [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

 

Алгоритм решения

Представленный в данной программе алгоритм достаточно объемный и содержит в себе большое количество вариантов поведения программы, поэтому разбирать его будем постепенно.
Начнем с функций, которые понадобятся в дальнейшем ходе решения:

  1. areCollinear — функция, принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.
    ( Основная формула:  [latex]\frac{x_1}{x_2}[/latex] [latex]=[/latex] [latex]\frac{y_1}{y_2}[/latex] )
  2. getMin — возвращает минимум двух чисел.
  3. getMax —  возвращает максимум двух чисел.
  4. projectionsIntersect — функция, принимающая абсциссы или ординаты двух векторов и возвращающая логическое значение true, если проекции отрезков на соответствующую ось пересекаются, и false в противном случае.
  5. getSlope — функция, принимающая координаты отрезка и возвращающая угол наклона прямой, на которой он расположен.
    ( Основная формула:  [latex]\frac{y_2 — y_1}{x_2 — x_1}[/latex] )
  6. getYIntercept — функция, принимающая координаты отрезка и возвращающая свободный член уравнения прямой, на которой он расположен.
    ( Основная формула:  [latex]\frac{x_2y_1 — x_1y_2}{x_2 — x_1}[/latex] )
  7. 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 тогда, когда это возможно, так как они будут задействованы в дальнейшем.

Теперь мы можем приступить к общему рассмотрению сложившейся ситуации, когда прямые параллельные оси ординат отсутствуют:

  1. Решим систему уравнений для двух заданных прямых и таким образом найдем точку их пересечения.
    [latex] \left\{\begin{matrix}
    k_1x + b_1 = y & \\
    k_2x + b_2 = y &
    \end{matrix}\right.[/latex]
  2. Найдя точку с координатами [latex](xIntersection,yIntersection)[/latex], следующим шагом станет проверка : принадлежит ли найденная точка имеющимся отрезкам. Для этого воспользуемся формулой скалярного произведения и определим косинус угла между векторами с началом в точке [latex](xIntersection, yIntersection)[/latex] и концами в соответствующих концах отрезка. Выполняем ее для двух отрезков. Если в обоих случаях найденный косинус будет [latex] \le[/latex] [latex]0[/latex], то точка находится на двух отрезках одновременно и  является их пересечением. Выводим сообщение «Intersect at point [latex](xIntersection, yIntersection)[/latex]«.
  3. В случае, если такая точка не найдена в следствие определенных причин, рассмотрим следующие возможные ситуации:
    а) При условии, что равны свободные члены уравнения прямых и точка не была найдена, можем проверить утверждение, что рассматриваемые прямые совпадают, а заданные отрезки находятся на ней. Здесь требуют рассмотрения  два варианта: отрезки накладываются, если проекции отрезков на ось абсцисс накладываются друг на друга, или же отрезки находятся на одной прямой и не пересекаются. Выводим соответствующее сообщение : «Overlap»/»On the same line, but don’t intersect».
    б) 
    Если свободные члены не равны и не выполнилось ни одно из предыдущих утверждений, приходим к выводу, что возможно отрезки, которые задают вектора, параллельны. Выполняем проверку на коллинеарность , в случае подтверждения предположения выводим сообщение : «Parallel».
    в) 
    Пройдя через все вышеупомянутые проверки и не получив логического значения true, определяем, что данные отрезки не пересекаются и не удовлетворяют ни одному из особенных случаев. Выводим сообщение : «Don’t intersect».Таким образом рассмотрение общего случая окончено. Перейдем ко второй ситуации:
  1. Если оба отрезка расположены на прямых вида [latex]x = a[/latex], то имеем следующие варианты:
    а) Если отрезки расположены на одной прямой и их проекции на ось ординат пересекаются, выводим сообщение : «Overlap».
    б) 
    Если отрезки расположены на одной прямой и их проекции на ось ординат не пересекаются, выводим сообщение : «On the same line, but don’t intersect».
    в) Если отрезки расположены не на одной прямой, выводим сообщение «Paralell».
  2. При условии, что только одна из прямых имеет вид [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».
    (В последних двух пунктах несколько раз координаты были записаны через черту, что , вероятно, требует пояснения: в этих ситуациях наблюдалось равенство и какую координату мы выберем не существенно).

Код программы:

Код программы

Аналогичная задача на сайте e-olymp:
839. Пересечение отрезков (Засчитанное решение)

А59и

Носуленко Марк
Носуленко Марк

Latest posts by Носуленко Марк (see all)

Даны действительные числа [latex]x, y[/latex]. Определить, принадлежит ли точка с координатами [latex]x, y[/latex] заштрихованной части плоскости.

А59и

 

Вычислил уравнения прямых по формуле :

[latex]\frac{x-x_{a}}{x_{b}-x_{a}}=\frac{y-y_{a}}{y_{a}-y_{b}}[/latex]

Получил уравнения :

[latex]y=2x+3[/latex], [latex]y=-x[/latex], [latex]y=\frac{x-1}{3}[/latex]

Плоскость разделил на верхнюю и нижнюю части осью ox([latex]y\geq 0[/latex], [latex]y\leq 0[/latex]), при помощи первых двух уравнений выделил заштрихованную область в верхней части, при помощи первого и третьего соответственно в нижней(изменив знак «=» на «≥» или «≤»(в зависимости от того где должна лежать точка для выполнения условия) ).

Тесты:

[latex]x[/latex] [latex]y[/latex] Результат:
-2 -1 Точка входит в заштрихованную область.
-2 -1.001 Точка не входит в заштрихованную область.
-2 -0.999 Точка не входит в заштрихованную область.
-1 1 Точка входит в заштрихованную область.
-1.001 1 Точка не входит в заштрихованную область.
-1 1.001 Точка не входит в заштрихованную область.
-1 0.999 Точка входит в заштрихованную область.
1 0 Точка входит в заштрихованную область.
1 -0.001 Точка не входит в заштрихованную область.

Сам код:

Ссылка на код

 

 

Ю2.5

Стеблинський Ігор Віталійович
Стеблинський Ігор Віталійович

Latest posts by Стеблинський Ігор Віталійович (see all)

Четырёхугольник ABCD задан координатами своих вершин на плоскости: A([latex]x_{a}[/latex],[latex]y_{a}[/latex]), B([latex]x_{b}[/latex],[latex]y_{b}[/latex]), C([latex]x_{c}[/latex],[latex]y_{c}[/latex]), D([latex]x_{d}[/latex],[latex]y_{d}[/latex]). Проверить, является ли он выпуклым.

Тесты:

Точки Координаты (x,y) Вердикт
A,B,C,D (1,1),(3,3),(5,2),(2,0) Выпуклый
A,B,C,D (-2,1),(2,2),(3,-1),(3,-1) Выпуклый
A,B,C,D (1,0),(1,3),(2,1),(5,0) Не выпуклый
A,B,C,D (-1,3),(0,0),(4,2),(-1,-3) Не выпуклый

Код программы:

Ссылка на код http://ideone.com/dsWBJc

Ссылка на код: ссылка

Ход решения:

Задаем уравнение прямой ([latex]\frac{x-x_{0}}{x_{1}-x_{0}}-\frac{y-y_{0}}{y_{1}-y_{0}}[/latex]). Преобразовываем его к виду без деления (чтобы не было проблем с делением на нуль) [latex](x-x_{0})*(y_{1}-y_{0})-(y-y_{0})*(x_{1}-x_{0})[/latex].

Для каждой стороны (AB,BC,CD,AD):

1. Строим уравнение прямой через эти две вершины.

2. Подставляем в формулу координаты остальных вершин.

3.Сравниваем значения вершин. Если их знаки разные — четырёхугольник не выпуклый.

Если для всех сторон данные условия выполнены — четырёхугольник является выпуклым.

А53

Зелінський Вячеслав Олександрович
Зелінський Вячеслав Олександрович

Latest posts by Зелінський Вячеслав Олександрович (see all)

Задача: Даны действительные числа [latex]a,b,c,d,e,f,g,h.[/latex] Известно, что точки [latex](e,f)[/latex] и [latex](g,h)[/latex] различны. Известно также, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] не лежат на прямой [latex]l[/latex], проходящей через точки [latex](e,f)[/latex] и [latex](g,h)[/latex]. Прямая [latex]l[/latex] разбивает координатную плоскость на две полуплоскости. Выяснить, верно ли, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] принадлежат одной и той же полуплоскости.

a b c d e f g h Комментарий:
1 1 1 1 1 1 1 1 (a,b) и (c,d) принадлежит
разным полуплоскостям
2 3 7 5 6 3 5 2 (a,b) и (c,d) принадлежат
одной полуплоскости
3 1545 3455 4 42 656,1 3445 1,56 (a,b) и (c,d) принадлежат
разным полуплоскостям

Код программы:

По условию задачи нужно выяснить, верно ли, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] принадлежат одной и той же полуплоскости. Вводим переменные с типом данных «float», так как координаты входят в множество действительных чисел.   Определяем  взаимное расположение точек с помощью  уравнения прямой:  [latex]f=(x-e)(h-f)-(y-f)(g-e)[/latex] .

Если точки лежат в одной полуплоскости, то [latex](a-e)*(h-f)-(b-f)*(g-e)[/latex] и
[latex](c-e)*(h-f)-(d-f)*(g-e)[/latex] – должны быть числами одного знака, если же их знаки противоположны, то точки лежат в разных полуплоскостях.

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом.

 

Код программы на Java: