23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // ccw
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Verified by
23dfcca431 2011-02-23        kinaba: //   - SRM 492 Div1 LV1
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
23dfcca431 2011-02-23        kinaba: double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: int ccw(const CMP& a, CMP b, CMP c) {
23dfcca431 2011-02-23        kinaba: 	b -= a; c -= a;
23dfcca431 2011-02-23        kinaba: 	if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
23dfcca431 2011-02-23        kinaba: 	if( outer_prod(b,c) < 0 ) return -1; // clockwise
23dfcca431 2011-02-23        kinaba: 	if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line
23dfcca431 2011-02-23        kinaba: 	if( norm(b) < norm(c) )   return -2; // [a--b]--c on line
23dfcca431 2011-02-23        kinaba: 	return 0; // [a--c--b] on line
ba015e9217 2014-10-04        kinaba: }
ba015e9217 2014-10-04        kinaba: 
ba015e9217 2014-10-04        kinaba: 
ba015e9217 2014-10-04        kinaba: // intersection of two line segments.
ba015e9217 2014-10-04        kinaba: bool cross(CMP p1, CMP p2, CMP P1, CMP P2) {
ba015e9217 2014-10-04        kinaba: 	return ccw(p1,p2,P1)*ccw(p1,p2,P2)<=0 && ccw(P1,P2,p1)*ccw(P1,P2,p2)<=0;
cb4efc4fe0 2016-06-15        kinaba: }
cb4efc4fe0 2016-06-15        kinaba: 
cb4efc4fe0 2016-06-15        kinaba: 
cb4efc4fe0 2016-06-15        kinaba: // Intersection of two line segments, by p1+(*pos)(p2-p1) where 0<=*pos<=1.
cb4efc4fe0 2016-06-15        kinaba: // only tested by local simple unittest. be careful.
cb4efc4fe0 2016-06-15        kinaba: template<typename T>
cb4efc4fe0 2016-06-15        kinaba: bool cross(const std::complex<T>& p1, const std::complex<T>& p2,
cb4efc4fe0 2016-06-15        kinaba:            const std::complex<T>& P1, const std::complex<T>& P2, T* pos) {
cb4efc4fe0 2016-06-15        kinaba: 	if( ccw(p1,p2,P1)*ccw(p1,p2,P2)<=0 && ccw(P1,P2,p1)*ccw(P1,P2,p2)<=0 ) {
cb4efc4fe0 2016-06-15        kinaba: 		if(outer_prod(p2-p1, P2-P1) == 0)
cb4efc4fe0 2016-06-15        kinaba: 			return false; // parallel
cb4efc4fe0 2016-06-15        kinaba: 		*pos = outer_prod(P1-p1, P2-P1) / outer_prod(p2-p1, P2-P1);
cb4efc4fe0 2016-06-15        kinaba: 		return true;
cb4efc4fe0 2016-06-15        kinaba: 	}
cb4efc4fe0 2016-06-15        kinaba: 	return false;
23dfcca431 2011-02-23        kinaba: }