параллельность | C++ для приматов

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

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

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

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

Координаты концов двух отрезков [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».
(В последних двух пунктах несколько раз координаты были записаны через черту, что , вероятно, требует пояснения: в этих ситуациях наблюдалось равенство и какую координату мы выберем не существенно).

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

#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;
}

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

[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	произвольный

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: параллельность

Mif 8

Задача

Тесты

Код

Решение

Related Images:

Ю2.15

Related Images: