Artifact 05f672d15009c4b53de46381ddfeb3a685fba3df
//-------------------------------------------------------------
// The circle passing three points
//
// Verified by
// - AOJ 0012 (only triangles)
//-------------------------------------------------------------
double outer_prod( CMP a, CMP b )
{
return (a.real()*b.imag() - b.real()*a.imag())/2;
}
bool point_in_polygon( vector<CMP>& ps, CMP p )
{
bool in = false;
for(int i=0; i<ps.size(); ++i) {
CMP a = ps[i] - p;
CMP b = ps[(i+1)%ps.size()] - p;
if(a.imag() > b.imag()) swap(a,b);
if(a.imag()<=0 && 0<b.imag()) {
if( outer_prod(a,b) < 0 )
in = !in;
}
//if( outer_prod(a,b)==0 && inner_prod(a,b)<=0 ) return ON;
}
return in;
}