fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. struct point //точка
  6. {
  7. 	double x;
  8. 	double y;
  9. };
  10. struct straight //прямая в виде общего уравнения Ax + By + C = 0
  11. {
  12. 	double A;
  13. 	double B;
  14. 	double C;
  15. };
  16. straight create_straight (point A, point B)
  17. {
  18. 	straight s;
  19. 	s.A = A.y - B.y;
  20. 	s.B = B.x - A.x;
  21. 	s.C = A.x * B.y - B.x * A.y;
  22. 	return s;
  23. }
  24. double r (point A, point B) //расстояние между двумя точками
  25. {
  26. 	return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));
  27. }
  28. point projection (point A, point B, point C) // проекция точки С на прямую AB
  29. {
  30. 	double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB
  31. 	double y = A.x - B.x;
  32. 	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));
  33. 	point H;
  34. 	H.x = C.x + x * L;
  35. 	H.y = C.y + y * L;
  36. 	return H;
  37. }
  38. point intersection (straight a, straight b) //точка пересечения прямых a и b
  39. {
  40. 	point ans;
  41. 	ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);
  42. 	ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);
  43. 	return ans;
  44. }
  45. void check_projection (point A, point B, point C, double & min_dis)
  46. {
  47. 	point H = projection(A,B,C);
  48. 	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))) //проекция принадлежит отрезку
  49. 	{
  50. 		if (r(H,C) < min_dis)
  51. 		{
  52. 			min_dis = r(H,C);
  53. 		}
  54. 	}
  55. }
  56. double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются
  57. {
  58. 	double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));
  59. 	check_projection (A,B,C,min_dis);
  60. 	check_projection (A,B,D,min_dis);
  61. 	check_projection (C,D,A,min_dis);
  62. 	check_projection (C,D,B,min_dis);
  63. 	return min_dis;
  64. }
  65. int main()
  66. {
  67. 	point A,B,C,D;
  68. 	cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;
  69. 	straight AB = create_straight(A,B);
  70. 	straight CD = create_straight(C,D);
  71. 	if (AB.A/CD.A == AB.B/CD.B) //условие паралельности прямых
  72. 	{
  73. 		cout<<distance_if_not_intersect(A,B,C,D);
  74. 	}
  75. 	else
  76. 	{
  77. 		point H = intersection(AB,CD);
  78. 		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)) && //точка пересечения принадлежит обоим отрезкам
  79. 		(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)) )
  80. 		{
  81. 			cout<<0;
  82. 		}
  83. 		else
  84. 		{
  85. 			cout<<distance_if_not_intersect(A,B,C,D);
  86. 		}
  87. 	}
  88. 	return 0;
  89. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
1 	-1 	3 	-1 	1 	2.5 	3 	3.5
stdout
copy 
3.5
https://ideone.com/qp9h6g
Расстояние между отрезками
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!