Задача взята со сборника задач Юркина А. Г.
Условие:
Найти расстояние между двумя произвольно заданными на плоскости отрезками.
Входные данные:
8 чисел, пары координат каждого конца отрезков.
Выходные данные:
Минимальное расстояние между отрезками.
Тесты:
| [latex]x_1[/latex] | [latex]y_1[/latex] | [latex]x_2[/latex] | [latex]y_2[/latex] | [latex]x_3[/latex] | [latex]y_3[/latex] | [latex]x_4[/latex] | [latex]y_4[/latex] | Минимальное расстояние |
| 0 | 0 | 2 | 2 | 1 | 1 | 0 | 3 | 0 |
| 1 | 2 | 3 | 2 | 2 | 1 | 2 | 0 | 1 |
| 1 | 1 | 3 | 1 | 1 | 2.5 | 3 | 2.5 | 1.5 |
| 1 | -1 | 3 | -1 | 1 | 2.5 | 3 | 3.5 | 3.5 |
Решение:
|
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <iostream> #include <cmath> #include <algorithm>//библиотека, содержащая функции min и max using namespace std; double perpendicularx(double x1,double y1, double x2, double y2, double x3, double y3) //функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок { double x; x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)); return x; } double perpendiculary(double x1,double y1, double x2, double y2, double x3, double y3, double x)//функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок { double y; y=(x-x1)*(y2-y1)/(x2-x1)+y1; return y; } int main() { double x, y, x1, x2, x3, x4, y1, y2, y3, y4, temp; cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4; double mini=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)); //предположим, что минимальное значение, это расстояние от конца одного отрезка до конца другого temp=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)); //для каждой пары концов разных отрезков высчитываем расстояние между ними if (temp<mini)//если оно меньше минимума mini=temp;//то меняем минимум temp=sqrt((x4-x1)*(x4-x1)+(y4-y1)*(y4-y1));//повторяем для каждой пары концов разных отрезков if (temp<mini) mini=temp; temp=sqrt((x4-x2)*(x4-x2)+(y4-y2)*(y4-y2)); if (temp<mini) mini=temp; x=perpendicularx(x1, y1, x2, y2, x3, y3);//получаем абциссу проекции конца одного отрезка на другой y=perpendiculary(x1, y1, x2, y2, x3, y3, x);//ординату if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0) //в случае, если равно нулю, абцисса будет равна бесконечности, а это возможно в том случае, если конец отрезка совпадает с его проекцией на другой отрезок { x=x3; // для корректных вычислений приравниваем абциссы и ординаты точки с её проекцией y=y3; } if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2)) //если проекция лежит на отрезке заданном { temp=sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y));//то проверяем, будет ли расстояние от конца отрезка до её проекции меньше, чем текущий минимум if (temp<mini) mini=temp;//если да, то меняем значение минимума } x=perpendicularx(x1, y1, x2, y2, x4, y4); // далее повторяемя для трех других концов отрезков y=perpendiculary(x1, y1, x2, y2, x4, y4, x); if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0) { x=x4; y=y4; } if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2)) { temp=sqrt((x4-x)*(x4-x)+(y4-y)*(y4-y)); if (temp<mini) mini=temp; } x=perpendicularx(x3, y3, x4, y4, x1, y1); y=perpendiculary(x3, y3, x4, y4, x1, y1, x); if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0) { x=x1; y=y1; } if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4)) { temp=sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y)); if (temp<mini) mini=temp; } x=perpendicularx(x3, y3, x4, y4, x2, y2); y=perpendiculary(x3, y3, x4, y4, x2, y2, x); if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0) { x=x2; y=y2; } if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4)) { temp=sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y)); if (temp<mini) mini=temp; } cout<<mini<<endl; // выводим минимальное расстояние и переходим на новую строку return 0; } |
Описание решения:
При решении задачи использовались переменные типа [latex]double[/latex], так как в условии не поставлено ограничение на координаты концов отрезков, а тип [latex]double[/latex] существенно расширяет диапазон вводимых значений. Решение данной задачи сводится к тому, чтобы найти расстояния между концами разных отрезков и длины перпендикуляров, опущенных с концов одного отрезка на другой. Поэтому, условно разобьем задачу на два пункта:
1.Нахождение расстояния между концами двух отрезков.
2.Нахождение длины перпендикуляров, опущенных с концов одного отрезка на другой.
1.Расстояние между двумя точками [latex]M_1(mx_1,my_1), M_2(mx_2,my_2)[/latex] находится по формуле [latex]\sqrt{(mx_2-mx_1)^2+(my_2-my_1)^2}[/latex]. Сначала, переменной [latex]mini[/latex] присваиваем значение расстояния между первой парой концов отрезков:
|
20 |
mini=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)); |
Далее, для всех остальных пар концов отрезков находим расстояние между ними, и если оно меньше чем [latex]mini[/latex], то меняем его значение.
После 4 проверок получаем минимальное расстояние между концами двух отрезков.
После этого переходим к пункту 2.
2. Для того, чтобы найти длину перпендикуляра, опущенного с конца одного отрезка на другой, необходимо решить систему, в которой первое уравнение — это уравнение прямой, содержащей концы отрезка, на который опускается перпендикуляр, а второе — уравнение прямой, содержащей этот перпендикуляр.
Продемонстрируем решение для отрезка с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex], и точки с координатами [latex](x_3, y_3)[/latex]
Первое уравнение имеет вид [latex](x-x_1)/(x_2-x_1)=(y-y_1)/(y_2-y_1)[/latex], а второе : [latex]-(x_2-x_1)/(y_2-y_1)*(x-x_3)=y-y_3[/latex]. Решив эту систему, получаем, что
|
8 |
x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)) |
и
|
14 |
y=(x-x1)*(y2-y1)/(x2-x1)+y1 |
Если делитель в [latex]x[/latex] равен нулю, то это означает, что проекция лежит на начале перпендикуляра, то есть они совпадают, и в таком случае присваиваем координатам проекции значения координат точки, с которой опускался перпендикуляр.
Получили абсциссу и ординату проекции точки на отрезок. Необходимо проверить, принадлежит ли эта проекция отрезку, для этого воспользуемся функциями [latex]min[/latex] и [latex]max[/latex], чтобы определить большие из координат отрезка, и операций сравнения:
|
37 |
if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2)) |
Если условия выполняются, то находим длину перпендикуляра по аналогии с расстоянием между концами отрезков, и сравниваем с [latex]mini[/latex]. Если длина меньше, то меняем значение минимума.
Так как все шаги нахождения повторяются 4 раза, то вынесем их в отдельные функции, которые высчитывают значения для каждой координаты проекции:
|
5 6 7 8 9 10 11 12 13 14 15 16 |
double perpendicularx(double x1,double y1, double x2, double y2, double x3, double y3) //функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок { double x; x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)); return x; } double perpendiculary(double x1,double y1, double x2, double y2, double x3, double y3, double x)//функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок { double y; y=(x-x1)*(y2-y1)/(x2-x1)+y1; return y; } |
После выполнения всех шагов, получаем минимальное расстояние между двумя отрезками.
Выводим его на экран и переходим на новую строку с помощью команды [latex]endl[/latex].
Здесь код программы на сайте ideone.com.
Вы не указали, какие именно пары точек образуют отрезки. Я предположил, что первые две точки задают первый отрезок, а вторая пара точек второй. Правильно?
Тогда почему для [(0 0) (1 1)] и [(1 0) (2 1)] расстояние 0? Добавьте этот случай к тестам, пожалуйста.