Artifact f28d7402b7cb45295c7d9e9e95e0544528580e75
//-------------------------------------------------------------
// The circle passing three points
//
// Verified by
// - AOJ 0012 (only triangles)
//-------------------------------------------------------------
double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
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;
}