線分と線分の交点 - プログラミング道場 ACM/ICPC

_p1と_p2,_p3と_p4によって作られる線分の交点を求める

typedef double		value;
typedef complex<value>	point;
 
value cross( point _a, point _b )
{ return _a.real() * _b.imag() - _a.imag() * _b.real(); }

value dot( point _a, point _b )
{ return _a.real() * _b.real() + _a.imag() * _b.imag(); }

bool OnToLine( point _p, point _p1, point _p2 )
{
	point a = _p1 - _p;
	point b = _p2 - _p;
	if( cross(a,b) != 0 ) return false;
	if( dot(a,b) > 0 )    return false;
	return true;
}
 
struct Line
{ value A,B,C; };

Line CreateLine( point _a, point _b )
{ 
	Line l;
	point t = _a - _b;
	l.A = - t.imag();
	l.B =   t.real();
	l.C = - cross(_a,_b);
	return l;
}

bool CollisionLine( point _p1, point _p2, point _p3, point _p4, value & _outX, value & _outY )
{
	Line l1 = CreateLine(_p1,_p2);
	Line l2 = CreateLine(_p3,_p4);
	
	value d = l2.B * l1.A - l1.B * l2.A;

	if( d == 0 ) return false;

	_outX = ( l1.B * l2.C - l2.B * l1.C ) / d;
	_outY = ( l2.A * l1.C - l1.A * l2.C ) / d;

	return OnToLine( point(_outX,_outY), _p1, _p2 );
}