struct POINT { float x, y; };
struct EDGE { POINT p[2]; };

bool intersect (float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, POINT *res=NULL)
{ float x1_x2=x1-x2, x3_x4=x3-x4, y1_y2=y1-y2, y3_y4=y3-y4;
float div=x1_x2*y3_y4-y1_y2*x3_x4;
if (div==0) return false;
float x1_y1_x2_y2=x1*y2-y1*x2, x3_y3_x4_y4=x3*y4-y3*x4,
x=(x1_y1_x2_y2*x3_x4-x1_x2*x3_y3_x4_y4)/div;
if ((x1-x)*(x2-x)>0 || (x3-x)*(x4-x)>0) return false;
if (res!=NULL) { float y=(x1_y1_x2_y2*y3_y4-y1_y2*x3_y3_x4_y4)/div;
(*res).x=x;
(*res).y=y; }
return true; }

inline bool intersect(POINT p1,POINT p2,POINT p3,POINT p4,POINT *res=NULL){ return intersect(p1.x,p1.y,p2.x,p2.y, p3.x,p3.y,p4.x,p4.y, res); }
inline bool intersect(EDGE e1, EDGE e2, POINT *res=NULL) { return intersect(e1.p[0],e1.p[1], e2.p[0],e2.p[1], res); }