Ю2.30. Расстояние между отрезками

Задача

Задача из сборника задач по программированию Юркина А.Г. 2002 г.
Найти расстояние между двумя между двумя произвольно заданными на плоскости отрезками [latex]AB[/latex] и [latex]CD[/latex].

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

Координаты концов первого отрезка [latex]A[/latex] [latex](x_a, y_a)[/latex], [latex]B[/latex] [latex](x_b, y_b)[/latex].
Координаты концов второго отрезка [latex]C[/latex] [latex](x_c, y_c)[/latex], [latex]D[/latex] [latex](x_d, y_d)[/latex].

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

Расстояние между отрезками [latex]min[/latex].

Тесты

 Входные данные  Выходные данные
 № [latex]x_a[/latex] [latex]y_a[/latex] [latex]x_b[/latex] [latex]y_b[/latex] [latex]x_c[/latex] [latex]y_c[/latex] [latex]x_d[/latex] [latex]y_d[/latex] [latex]min[/latex]
 1  1  1  2  1  3  1  4  1  1
 2  0  0  5  5  1  1  2  2  0
 3  0  1  3  3  5  3  6  4  2
 4  0  0  7  0  0  8  5  3  3
 5  5  5  10  10  5  9  6  12  2.8284
 6  2  1  3  5  0  0  0  5  2
 7  -3  0  3  0  0  -3  0  3  0

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

Решение

Для начала проверим не пересекаются ли отрезки. Пусть для отрезка [latex]AB[/latex] [latex]x=t(x_b-x_a)+x_a[/latex], [latex]y=t(y_b-y_a)+y_a[/latex], а для [latex]CD[/latex] [latex]x=s(x_d-x_c)+x_c[/latex], [latex]y=s(y_d-y_c)+y_c[/latex] (где [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex] ). Если отрезки пересекаются, то выполняются равенства: [latex]t(x_b-x_a)-s(x_d-x_c)=x_c-x_a[/latex] и [latex]t(y_b-y_a)-s(y_d-y_c)=y_c-y_a[/latex]. Полученную систему уравнений решим методом Крамера: 
[latex]\Delta =\begin{pmatrix} x_b-x_a & \quad x_c-x_d \\ y_b-y_a & \quad y_c-y_d \end{pmatrix}=(x_b-x_a)(y_c-y_d)-(y_b-y_a)(x_c-x_d)[/latex] [latex]\Delta _1=\begin{pmatrix} x_{ b }-x_{ a } & \quad x_{ c }-x_{ a } \\ y_{ b }-y_{ a } & \quad y_{ c }-y_{ a } \end{pmatrix}=(x_b-x_a)(y_c-y_a)-(y_b-y_a)(x_c-x_a)[/latex] [latex]\Delta _2=\begin{pmatrix} x_{ c }-x_{ a } & \quad x_{ c }-x_{ d } \\ y_{ c }-y_{ a } & \quad y_{ c }-y_{ d } \end{pmatrix}=(y_c-y_d)(x_c-x_a)-(x_c-x_d)(y_c-y_a)[/latex].
Тогда [latex]t=\frac { \Delta_1 }{ \Delta } [/latex], а [latex]s=\frac { \Delta_2 }{ \Delta } [/latex]. Если [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex], а [latex]\Delta \neq 0[/latex], то отрезки пересекаются и расстояние между ними [latex]min[/latex] равно [latex]0[/latex], иначе с каждого конца отрезка попытаемся опустить высоту на противоположный. Если отрезок, на который опускаем высоту вертикальный, то поменяем местами координаты каждого конца отрезка и точки, с которой опускаем высоту (таким образом сохраним расстояние между точкой и отрезком, а отрезок станет горизонтальным). Пусть [latex]k[/latex] и [latex]d[/latex] — коэффициенты уравнения прямой, на которую опущена эта высота. Основание высоты будет находится на прямой в точке  [latex]Z[/latex], координаты [latex]Z[/latex] [latex](x_z, y_z)[/latex] можно найти по формуле [latex]y_z=kx_z+d[/latex]. Поскольку высота перпендикулярна отрезку — скалярное произведение их векторов равно [latex]0[/latex]. Тогда [latex](x_2-x_1)(x_3-x_z)+(y_2-y_1)(y_3-y_z)=0[/latex], соответственно [latex]x_z=\frac { x_3x_2-x_3x_1+y_2y_3-y_1y_3+y_1d-y_2d }{ ky_2-ky_1+x_2-x_1 } [/latex] (где [latex](x_3, y_3)[/latex] — координаты точки, с которой была опущена высота, [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] — координаты концов отрезка, принадлежащего прямой на которую опущена высота). Вычислим длину [latex]dl[/latex] каждой высоты, основание которой принадлежит одному из данных отрезков: [latex]dl=\sqrt { {(x_3-x_z)}^{2}+{(y_3-x_zk-d)}^{2} }[/latex](где [latex] (x_3, y_3)[/latex] — координаты точки, с которой была опущена высота). Минимальная длина высоты и будет наименьшим расстоянием между отрезками. В случае, если невозможно опустить высоты из одного отрезка на другой: расстояние между ними будет равно минимальному расстоянию между концами двух отрезков [latex]min=\sqrt { {( x_1-x_3) }^{ 2 }+{ (y_1-y_3) }^{ 2 } }[/latex] (где [latex](x_1, y_1)[/latex] — координаты одного из концов первого отрезка, а [latex](x_3, y_3)[/latex] — координаты одного из концов второго отрезка) .

Ссылки

Mif 17.13

17_13

Задача №17.13

Условие

Принадлежит ли точка (х;у) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты

Входные данные (точка K) Выходные данные
(3;4) no
(1;1) yes
(1;4) yes
(3;0) yes
(0;6) no
(-13; -3) no
(-4.5; -3) yes

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

Для запроса на выполнение нажать здесь.

Решение

[latex](x — x_A)(y_B — y_A) — (y — y_A)(x_B — x_A) = 0[/latex] — уравнение прямой, проходящей через точки [latex]A[/latex] и [latex]B[/latex]. Тогда для любой точки [latex](x; y)[/latex] можно определить её местоположение относительно прямой [latex]AB[/latex]. Если левая часть неравенства будет равно 0, то точка лежит на прямой. Прямая [latex]AB[/latex] разбивает плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения, а точки из другой полуплоскости — отрицательные. Тогда, объединением условий местоположения точки [latex](x; y)[/latex] и местоположения точек [latex]C, A, B[/latex] относительно прямых [latex]AB[/latex], [latex]BC[/latex], [latex]AC[/latex] соответственно, мы сможем определить местоположение данной точки относительно треугольника.

По рисунку видно, что [latex]A(1;4), B(5, -4), C(-5, -3)[/latex]. Тогда, определяем положение точки [latex]K[/latex] относительно каждой прямой и точки не лежащей на данной прямой треугольника [latex]ABC[/latex].

 

Ю1.26

Сіренко Валерія Сергіївна
Сіренко Валерія Сергіївна

Latest posts by Сіренко Валерія Сергіївна (see all)

Задача:

Треугольник задается координатами своих вершин на плоскости : [latex]A(x_{1} , y_{2})[/latex] , [latex]B(x_{2} , y_{2})[/latex] , [latex]C(x_{3} , y_{3})[/latex] . Найти длину и основание высоты, опущенной из вершины A на сторону ВС.

Тесты

[latex]x_{А}[/latex] [latex]y_{A}[/latex] [latex]x_{B}[/latex] [latex]y_{B}[/latex] [latex]x_{C}[/latex] [latex]y_{C}[/latex] Основание ([latex]BC[/latex]) Высота[latex]h[/latex] Комментарий
7 9 45 9 34 5 11 13 пройден
0.75 1 0.25 2 0.5 3 1 0 пройден
98 67 56 47 34 95 52 47 пройден
0 1 0 3 0 4 1 0 пройден

В четвертом  примере имеем вырожденный треугольник, для которого площадь будет равна нулю , следовательно и высота так же равна 0

Код:

ссылка на C++ : http://ideone.com/fBfd8S

ссылка на Java : http://ideone.com/ut9G6J

 

Решение:

Для начала находим стороны треугольника :

далее выполняем условие , что если сумма двух сторон меньше третей то треугольник не существует. Если же наоборот начинаем считать плащадь треугольника по формуле :

и с помощью площади находим высоту :

и в конце выводим высоту и основание.

А59ж

Сіренко Валерія Сергіївна
Сіренко Валерія Сергіївна

Latest posts by Сіренко Валерія Сергіївна (see all)

Задача

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

Безымянный

Тесты:

x y результат комментарий
-1.5 1 outside пройден
-0.5 0.5 inside пройден
0.5 0.5 inside пройден
1.5 1.5 outside пройден
-0.5 -0.5 inside пройден
-1 -1.5 outside пройден
1 -1.5 outside пройден
 

Ссылка на код C++ : http://ideone.com/JKdLjg

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

Решение :

Решение задачи сводится к поиску условия, при котором точка будет принадлежать данной части плоскости. Далее вводим оператор условия «if» и ставим ограничения на [latex]x[/latex] и [latex]y[/latex].

Анализируем условие , при каких значениях [latex]x[/latex] и [latex]y[/latex] точка будет принадлежать условию , а при каких нет.Если вошла точка по координатам во все области -> точка принадлежит треугольнику или же наоборот .