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