fork(6) download
copy 
  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
comments (?)
stdin
copy 
1 1 5 4 1 3 5 3
stdout
copy 
Intersect at a point (3.66667,3)
https://ideone.com/JqFg74
Ю2.15!!!!!
language:
C++14 (gcc 8.3)
created:
9 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!