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

_aと_bを結ぶ線分と_centerを中心とする半径_rの円との交点を求める

int CircleAndLine( point _a, point _b, point _center, value _r, point & _out1, point & _out2 )
{ 
	value a,b,c;
	{
                    Line l = CreateLine( _a - _center ,_b - _center );
                    a = l.A; b = l.B; c = l.C;
	}

	value ab =  a * a + b * b;
	value ac =  a * c;
	value bc =  b * c;
	value r  = _r *_r * ab - c * c;

	if( r < 0  ) return 0;

	if( r == 0 ) // l*-ab < r < l*ab
	{
		value x = - ac / ab;
 		value y = - bc / ab;
		_out1 = _out2 = point( x, y ) + _center;
		return OnToLine( _out1, _a, _b ) ? 1 : 0;
	}

	r  = sqrt(r);	
	value x1 = ( - ac - b * r ) / ab;
	value y1 = ( - bc + a * r ) / ab;
	value x2 = ( - ac + b * r ) / ab;
	value y2 = ( - bc - a * r ) / ab;

	_out1 = point(x1,y1) + _center;
 	_out2 = point(x2,y2) + _center;

	int flg= 0;
	flg += OnToLine( _out1, _a, _b ) ? 1 : 0;
	flg += OnToLine( _out2, _a, _b ) ? 2 : 0;

	return flg;
}