计算几何模板

判断两线段是否相交：点击查看

struct node{
	double x;
	double y;
}; 
bool judge(node a,node b,node c,node d)
{
	if(min(a.x,b.x) <= max(c.x,d.x) && min(c.x,d.x) <= max(a.x,b.x) && min(a.y,b.y) <= max(c.y,d.y) &&min(c.y,d.y)<=max(a.y,b.y))
	{
		
		double u,v,w,z;
                u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
                v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);
                w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
                z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);
        
                return (u*v<=0.00000001 && w*z<=0.00000001);
	}
	return false;
}