Задача
Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин на плоскости.
Тесты
| Входные данные | Результат работы программы |
| 1 1 1 7 5 3 1 6 |
0 |
| 5 6 8 8 2 2 5 4 |
2 |
| 1 -1 1 -3 2 -2 4 -1 |
1 |
| -5 -1 -5 -3 -2 -1 -3 -2 |
2 |
| -1 1 -1 3 -4 2 -3 5 |
2.52982 |
| 1 4 3 6 3 4 5 4 |
1.41421 |
Код программы
|
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 85 86 87 88 89 |
#include <iostream> #include <cmath> using namespace std; struct point //точка { double x; double y; }; struct straight //прямая в виде общего уравнения Ax + By + C = 0 { double A; double B; double C; }; straight create_straight (point A, point B) { straight s; s.A = A.y - B.y; s.B = B.x - A.x; s.C = A.x * B.y - B.x * A.y; return s; } double r (point A, point B) //расстояние между двумя точками { return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y)); } point projection (point A, point B, point C) // проекция точки С на прямую AB { double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB double y = A.x - B.x; double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x)); point H; H.x = C.x + x * L; H.y = C.y + y * L; return H; } point intersection (straight a, straight b) //точка пересечения прямых a и b { point ans; ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B); ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A); return ans; } void check_projection (point A, point B, point C, double & min_dis) { point H = projection(A,B,C); if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку { if (r(H,C) < min_dis) { min_dis = r(H,C); } } } double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются { double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D))); check_projection (A,B,C,min_dis); check_projection (A,B,D,min_dis); check_projection (C,D,A,min_dis); check_projection (C,D,B,min_dis); return min_dis; } int main() { point A,B,C,D; cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y; straight AB = create_straight(A,B); straight CD = create_straight(C,D); if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых { cout<<distance_if_not_intersect(A,B,C,D); } else { point H = intersection(AB,CD); if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам (H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) ) { cout<<0; } else { cout<<distance_if_not_intersect(A,B,C,D); } } return 0; } |
Решение
Основная идея состоит в том, что расстояние между непересекающимися отрезками [latex]AB[/latex] и [latex]CD[/latex] — это минимальная из длин, соединяющих вершины разных отрезков, и длин перпендикуляров, проведенных из вершины на противоположный отрезок. Подробнее о математической части поиска перпендикуляра тут. Кроме этого, отрезки могут пересекаться, что проверяется отдельно. В таком случае, расстояние между ними равно нулю.
Чтобы проверить, пересекаются ли отрезки, нужно сначала проверить, не параллельны ли они.Если они не параллельны, нужно найти точку пересечения прямых, на которых лежат отрезки, а затем проверить принадлежит ли она обоим отрезкам. Отрезки пересекаются тогда и только тогда, когда они лежат на пересекающихся прямых, точка пересечения которых принадлежит обоим отрезкам. Координаты точки пересечения находятся из системы уравнений прямых, на которых лежат отрезки.
[latex] \begin{cases} A_{1}x + B_{1}y + C_{1} = 0 \\ A_{2}x + B_{2}y + C_{2} = 0 \end{cases} [/latex]
Из первого уравнения: [latex]x = \frac{-B_{1}y-C_{1}}{A_{1}}[/latex]
Подставим [latex]x[/latex] во второе уравнение:
[latex] \frac{A_{2}}{A_{1}}(-B_{1}y-C_{1}) + B_{2}y + C_{2} = 0[/latex] [latex](*)[/latex]Решив уравнение [latex](*)[/latex] получим:
[latex]y = \frac{C_{1}A_{2}-C_{2}A_{1}}{A_{1}B_{2}-A_{2}B_{1}}[/latex].Тогда
[latex]x = \frac{C_{2}B_{1}-C_{1}B_{2}}{A_{1}B_{2}-A_{2}B_{1}}[/latex]
Каким-то образом оказалось две одинаковые задачи. Проверьте, пожалуйста, на тестах из этой статьи.
Проверил. Результаты полностью совпадают.