23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // Convex Hull -- Andrew's Monotone Chain
23dfcca431 2011-02-23        kinaba: //   O(N log N)
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Verified by
23dfcca431 2011-02-23        kinaba: //   - SRM 336 Div1 LV3
23dfcca431 2011-02-23        kinaba: //   - TCO09 Round2 LV2
23dfcca431 2011-02-23        kinaba: //   - SRM 486 Div1 LV3
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;
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: bool byX( const CMP& a, const CMP& b ) {
23dfcca431 2011-02-23        kinaba: 	if( a.real() != b.real() )
23dfcca431 2011-02-23        kinaba: 		return a.real() < b.real();
23dfcca431 2011-02-23        kinaba: 	return a.imag() < b.imag();
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: vector<CMP> convex_hull( vector<CMP> p )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	#define IS_RIGHT <0   // skip on-line verts
23dfcca431 2011-02-23        kinaba: 	//#define IS_RIGHT ==-1 // take all
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	sort(p.begin(), p.end(), &byX);
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	vector<CMP> ans;
23dfcca431 2011-02-23        kinaba: 	for(int i=0; i<p.size(); ans.push_back(p[i++])) // left-to-right
23dfcca431 2011-02-23        kinaba: 		while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
23dfcca431 2011-02-23        kinaba: 			ans.pop_back();
23dfcca431 2011-02-23        kinaba: 	if( ans.size() == p.size() )
23dfcca431 2011-02-23        kinaba: 		return ans;
23dfcca431 2011-02-23        kinaba: 	for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left
23dfcca431 2011-02-23        kinaba: 		while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
23dfcca431 2011-02-23        kinaba: 			ans.pop_back();
23dfcca431 2011-02-23        kinaba: 	ans.pop_back();
23dfcca431 2011-02-23        kinaba: 	return ans;
23dfcca431 2011-02-23        kinaba: }