←  Геометрия

олимпиадники-информатики

»

Пересечение двух отрезков

yanush фотография yanush 31 янв 2015

struct point{
double x;
double y;
};
struct vec{
double x;
double y;
};
bool perlo(point x1, point x2, point x3, point x4){
const double INF = 1000000000000;
bool ans = false;
vec q,p;
q.x = x1.x-x2.x;
q.y = x1.y-x2.y;
p.x = x3.x-x4.x;
p.y = x3.y-x4.y;
double x = 0;
double y = 0;
double r = 0;
double b = (x3.y*q.x-x1.y*q.x-x3.x*q.y+x1.x*q.y)
	/ (p.x*q.y-p.y*q.x);
if(p.x*q.y-p.y*q.x == 0){
  r = abs((x1.x-x3.x)*p.y - (x1.y-x3.y)*p.x);
  if( r<0.000000001 ){
   x = INF;
  }else{
   x = -INF;
  }
}
if(p.x*q.y-p.y*q.x != 0){
  x = x3.x+p.x*b;
  y = x3.y+p.y*b;
}
if(x == INF){
  if( (((x1.x <= x3.x && x1.x >= x4.x) || (x1.x >= x3.x && x1.x <= x4.x))
   &&((x1.y <= x3.y && x1.y >= x4.y) || (x1.y >= x3.y && x1.y <= x4.y))) ||
   (((x2.x <= x3.x && x2.x >= x4.x) || (x2.x >= x3.x && x2.x <= x4.x))
   &&((x2.y <= x3.y && x2.y >= x4.y) || (x2.y >= x3.y && x2.y <= x4.y)))
	) ans = true;
}
if( (((x <= x1.x && x >= x2.x) || ( x >= x1.x && x <= x2.x))
  &&((y <= x1.y && y >= x2.y) || ( y >= x1.y && y <= x2.y)))
      	&&
   (((x <= x3.x && x >= x4.x) || ( x >= x3.x && x <= x4.x))
  &&((y <= x3.y && y >= x4.y) || ( y >= x3.y && y <= x4.y)))
   ) ans = true;
//cout <<x <<endl <<y<<endl;
return ans;

// (x,y) - точка пересечения прямых.
// ans - имеют ли отрезки общие точки
}
Ответить