Condition to verify if a point C in a segment [A,B]
min(A.x,B.x) <= C.x <= max(A.x,B.x) (2)
min(A.y,B.y) <= C.y <= max(A.y,B.y) (3)
I forget to check (2),(3); only remember 1. (AC if i remember)
vihrov: Another way: if we have a segment AB and a point C, then C is in AB iff AC + CB = AB.
Condition to check angle (AB,AC) <= 90.
- Using AB*AB+AC*AC>BC*BC
- Using atan2 : it may lead to error of precision (I found it during contest).
dAFTc0d3r: Easier way to check sign of cos
( AB, BC ) = | AB | * | BC | * cos( angleABC )
| AB | * | BC | > 0
So sign cos( angleABC ) = sign ( AB, BC ) = AB.x * BC.x + AB.y * BC.y
( AB, BC ) = | AB | * | BC | * cos( angleABC )
| AB | * | BC | > 0
So sign cos( angleABC ) = sign ( AB, BC ) = AB.x * BC.x + AB.y * BC.y
It had better been multiplication :)
Suppose that segment lies on X axis and point is offset from segment by small value 'eps'. When one finds AC using
sqrt(dx^2+dy^2)
following occurs
sqrt (large_value^2 + eps^2)
( AB, BC ) = | AB | * | BC | * cos( angleABC )
| AB | * | BC | > 0
So sign cos( angleABC ) = sign ( AB, BC ) = AB.x * BC.x + AB.y * BC.y
bool belongs_good( point A, otr o )
{
double tx, ty;
bool uncalcx = false, uncalcy = false;
if ( o.A.x == o.B.x )
uncalcx = true;
else
tx = double( A.x - o.A.x ) / ( o.B.x - o.A.x );
if ( o.A.y == o.B.y )
uncalcy = true;
else
ty = double( A.y - o.A.y ) / ( o.B.y - o.A.y );
if ( uncalcx )
tx = ty;
if ( uncalcy )
ty = tx;
return ( tx == ty && tx >= 0 && tx <= 1 );
}
P.S.: In problem B I use
return ( tx == ty && tx >= 0.2 && tx <= 0.8 );
because of 1/4 condition.