Artifact Content
Not logged in

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;
}