Mif 8

Задача

Условие взято отсюда

Четырёхугольник [latex]ABCD[/latex] задан на плоскости целочисленными координатами вершин. Определите тип четырёхугольника: квадрат, ромб, прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Из характеристик указать наиболее частную.

Тесты

[latex]a_1[/latex]   [latex]a_2[/latex] [latex]b_1[/latex] [latex]b_2[/latex] [latex]c_1[/latex][latex]c_2[/latex] [latex]d_1[/latex] [latex]d_2[/latex]                                                   Ответ
0 0 1 0 1 1 0 1   квадрат
0 -3 2 0 0 3 -2 0 ромб
0 0 4 0 4 1 1 4 прямоугольник
0 0 10 0 12 4 2 4 пaраллелограмм
0 0  2 0  1 1  0 1 трапеция
0 0  0 2  1 1  1 0 трапеция
-4 -5 -15 7 5 8 6 -7 произвольный
 0 0 1 0 10 20  -5 7 произвольный

 

Код

 

Решение

Для начала стоит найти длины всех сторон:

[latex]AB^{2}=((a1-b1)^{2}+(a2-b2)^{2})[/latex]. (аналогично для остальных сторон)

Затем можно найти длины диагоналей четырёхугольника

[latex]AC^{2}=((a1-c1)^{2}+(a2-c2)^{2})[/latex]. (аналогично для [latex]BD[/latex]).

Через условие задаем равность противоположных сторон [latex]AB=CD[/latex] и  [latex]BC=DA[/latex]:

  1. У ромба смежные стороны равны, но если у ромба диагонали равны, то это квадрат;
  2. Если четырёхугольник не является квадратом, но диагонали равны, то это прямоугольник;
  3. В противном случае — параллелограмм.

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

Код на ideone

Ю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. Пересечение отрезков (Засчитанное решение)