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