fork(5) download
  1. #include <iostream>
  2. #include <math.h>
  3. using namespace std;
  4.  
  5. bool areCollinear(double x1, double y1, double x2, double y2) {
  6. return x1 / x2 == y1 / y2 ? true : false;// проверка на коллинеарность
  7. }
  8.  
  9. double getMin(double x1, double x2) {
  10. return x1 < x2 ? x1 : x2;
  11. }
  12.  
  13. double getMax(double x1, double x2) {
  14. return x1 > x2 ? x1 : x2;
  15. }
  16.  
  17. // Проверка на пересечение проекций на оси, посредством нахождения взаимного расположения концов проекций
  18. bool projectionsIntersect(double x1, double x2, double x3, double x4) {
  19. return ((getMin(x1, x2) <= getMin(x3, x4) && getMin(x3, x4) <= getMax(x1, x2)) || ((getMin(x3, x4) <= getMin(x1, x2) && getMin(x1, x2) <= getMax(x3,x4))));
  20. }
  21.  
  22. // Вычисление коэффициента угла наклона уравнения прямой
  23. double getSlope(double x1, double y1, double x2, double y2) {
  24. return (y2 - y1) / (x2 - x1);
  25. }
  26.  
  27. // Вычисление свободного члена уравнения прямой
  28. double getYIntercept(double x1, double y1, double x2, double y2) {
  29. return (x2 * y1 - x1 * y2) / (x2 - x1);
  30. }
  31.  
  32. // Нахождение косинуса угла между векторами
  33. double getCos(double x1, double y1, double x2, double y2) {
  34. return (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) + sqrt(x2 * x2 + y2 * y2));
  35. }
  36.  
  37. int main() {
  38. double slope1, slope2; // Коэффициенты углов наклона уравнений прямых, на которых расположены отрезки
  39. bool f1 = false, f2 = false; // Логические флаги для прямых вида x = a
  40. double yIntercept1, yIntercept2; // Свободные члены уравнений прямых, на которых расположены отрезки
  41. double xIntersection, yIntersection; // Координаты точки пересечения, если она существует
  42. double x1, y1, x2, y2, x3, y3, x4, y4; // Заданные координаты концов отрезков
  43. cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
  44. double vx1 = x2 - x1;
  45. double vy1 = y2 - y1; // Вычислим координаты векторов,
  46. double vx2 = x4 - x3; // Задаваемых данными отрезками
  47. double vy2 = y4 - y3;
  48. slope1 = (vx1 != 0 ? getSlope(x1, y1, x2, y2) : 0); // Для прямых вида x = a
  49. slope2 = (vx2 != 0 ? getSlope(x3, y3, x4, y4) : 0); // Присваиваем значение 0 коэффициенту угла наклона
  50. vx1 != 0 ? yIntercept1 = getYIntercept(x1, y1, x2, y2) : f1 = true; // Для прямых вида x = a
  51. vx2 != 0 ? yIntercept2 = getYIntercept(x3, y3, x4, y4) : f2 = true; // Присваиваем флагу значение true
  52. if (!f1 && !f2) {
  53. xIntersection = (yIntercept2 - yIntercept1) / (slope1 - slope2); // Находим решение системы уравнений
  54. yIntersection = slope1 * xIntersection + yIntercept1;
  55. if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) // Проверяем находится ли точка на обоих отрезках
  56. cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";
  57. else if (yIntercept1 == yIntercept2) {
  58. if (projectionsIntersect(x1, x2, x3, x4))
  59. cout << "Overlap";
  60. else
  61. cout << "On the same line, but don't intersect";
  62. }
  63. else if (yIntercept1 != yIntercept2 && (areCollinear(vx1, vy1, vx2, vy2) || (y1 == y2 && y3 == y4)))
  64. cout << "Paralell";
  65. else
  66. cout << "Don't intersect";
  67. } // Блок нахождения расположения для всех отрезков, кроме тех, где хотя бы один из них расположен на прямой вида x = a
  68. else {
  69. if (slope1 == 0 && slope2 == 0 && f1 && f2) {
  70. if (x1 == x4 && projectionsIntersect(y1, y2, y3, y4))
  71. cout << "Overlap";
  72. else if (x1 != x4)
  73. cout << "Paralell";
  74. else
  75. cout << "On the same line, but don't intersect";
  76. } // Блок для двух прямых вида x = a
  77. else if (f1 ^ f2 && slope1 == 0 && slope2 == 0) {
  78. if (f1) {
  79. swap(x1, x3);
  80. swap(x2, x4);
  81. swap(y1, y3);
  82. swap(y2, y4);
  83. swap(yIntercept1, yIntercept2);
  84. }
  85. yIntersection = y1;
  86. xIntersection = x3;
  87. if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0)
  88. cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";
  89. else
  90. cout << "Don't intersect";
  91. } // Блок для прямых вида y = b и x = a
  92. else if (slope1 == 0 ^ slope2 == 0) {
  93. if (slope1 == 0) {
  94. swap(x1, x3);
  95. swap(x2, x4);
  96. swap(y1, y3);
  97. swap(y2, y4);
  98. swap(yIntercept1, yIntercept2);
  99. }
  100. xIntersection = x3;
  101. yIntersection = x3 + yIntercept1;
  102. if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0)
  103. cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";
  104. else
  105. cout << "Don't intersect";
  106. } // Блок нахождения расположения, когда только одна пряма имеет вид x = a, а вторая y = kx +b
  107. } // Блок нахождения расположения, если хотя бы один отрезок находится на прямой вида x = a
  108. return 0;
  109. }
Success #stdin #stdout 0s 3420KB
stdin
1 1 5 4 1 3 5 3
stdout
Intersect at a point (3.66667,3)