Задача
Задача из сборника задач по программированию Юркина А.Г. 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 |
Код программы
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 |
#include <iostream> #include <cmath> using namespace std; double ras(double x1, double y1, double x2, double y2, double x3, double y3){ double k,d; if(x1==x2){ //Если отрезок вертикальный - меняем местами координаты каждой точки. swap(x1, y1); swap(x2, y2); swap(x3, y3); } k=(y1-y2)/(x1-x2);//Ищем коэффициенты уравнения прямой, которому принадлежит данный отрезок. d=y1-k*x1; double xz=(x3*x2-x3*x1+y2*y3-y1*y3+y1*d-y2*d)/(k*y2-k*y1+x2-x1); double dl=-1; if((xz<=x2&&xz>=x1)||(xz<=x1&&xz>=x2)) dl=sqrt((x3-xz)*(x3-xz)+(y3-xz*k-d)*(y3-xz*k-d));//Проверим лежит ли основание высоты на отрезке. return dl; } int main() { double xa, xb, ya, yb, xc, xd, yc, yd, dl, dl1, dl2, dl3, dl4, min=-1,o,o1,o2,t=-2,s=-2; cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd; o=(xb-xa)*(-yd+yc)-(yb-ya)*(-xd+xc); o1=(xb-xa)*(yc-ya)-(yb-ya)*(xc-xa); o2=(-yd+yc)*(xc-xa)-(-xd+xc)*(yc-ya); if(o!=0){ t=o1/o; s=o2/o; } if((t>=0&&s>=0)&&(t<=1&&s<=1))min=0;//Проверим пересекаются ли отрезки. else{ //Найдём наименьшую высоту опущенную из конца одного отрезка на другой. dl1=ras(xa,ya,xb,yb,xc,yc); min=dl1; dl2=ras(xa,ya,xb,yb,xd,yd); if((dl2<min&&dl2!=-1)||min==-1)min=dl2; dl3=ras(xc,yc,xd,yd,xa,ya); if((dl3<min&&dl3!=-1)||min==-1)min=dl3; dl4=ras(xc,yc,xd,yd,xb,yb); if((dl4<min&&dl4!=-1)||min==-1)min=dl4; if(min==-1){ //В случае, если невозможно опустить высоту найдём минимальное расстояние между точками. dl1=sqrt((xa-xc)*(xa-xc)+(ya-yc)*(ya-yc)); min=dl1; dl2=sqrt((xb-xd)*(xb-xd)+(yb-yd)*(yb-yd)); if(dl2<min)min=dl2; dl3=sqrt((xb-xc)*(xb-xc)+(yb-yc)*(yb-yc)); if(dl3<min)min=dl3; dl4=sqrt((xa-xd)*(xa-xd)+(ya-yd)*(ya-yd)); if(dl4<min)min=dl4; } } cout<<min; return 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] — координаты одного из концов второго отрезка) .
Ссылки
- Код программы
- Условие задачи (страница 32).
— Вы пишите «найдём неизвестные уравнений», лучше «найдём коэффициенты уравнений». А вообще переход к такой форме записи идея не самая удачная. Сразу появляется куча кода для обработки нулей в знаменателях для вертикальных прямых. Лучше использовать параметрическую форму записи отрезков. Тогда и легче определить принадлежность точки пересечения отрезкам.
— Не очень удачные обозначения. Лучше обозначить отрезки [latex]\left[AB\right][/latex] и [latex]\left[CD\right][/latex]. Тогда координаты точек естественно будет обозначить [latex]A\left(x_a,y_a\right),[/latex] [latex]B\left(x_b,y_b\right),[/latex] [latex]C\left(x_c,y_c\right)[/latex] и [latex]D\left(x_d,y_d\right).[/latex]
Спасибо. Постарался всё исправить. Избежал случаи с нулём в знаменателе.
Зачёл.
Длинный код с логическими повторами, который сложно анализировать. Лечится использованием вспомогательных функций. Точно нужна функция для вычисления кратчайшего расстояния от точки до отрезка и просто расстояние между двумя точками.
Если будет свободное время попробуйте сделать еще один вариант кода. Если разместить здесь оба варианта кода, то станет очевидна разница в размере и читаемости.