Artifact 75743e110118c49cd9a8cce9408438c0745cd246

• File _lib/geo/convexHull.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/geo/convexHull.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

//-------------------------------------------------------------
// Convex Hull -- Andrew's Monotone Chain
//   O(N log N)
//
// Verified by
//   - SRM 336 Div1 LV3
//   - TCO09 Round2 LV2
//   - SRM 486 Div1 LV3
//-------------------------------------------------------------

double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); }

int ccw(const CMP& a, CMP b, CMP c) {
	b -= a; c -= a;
	if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
	if( outer_prod(b,c) < 0 ) return -1; // clockwise
	if( inner_prod(b,c) < 0 ) return +2; // c--a--b on line
	if( norm(b) < norm(c) )   return -2; // a--b--c on line
	return 0;
}

bool byX( const CMP& a, const CMP& b ) {
	if( a.real() != b.real() )
		return a.real() < b.real();
	return a.imag() < b.imag();
}

vector<CMP> convex_hull( vector<CMP> p )
{
	#define IS_RIGHT <0   // skip on-line verts
	//#define IS_RIGHT ==-1 // take all

	sort(p.begin(), p.end(), &byX);

	vector<CMP> ans;
	for(int i=0; i<p.size(); ans.push_back(p[i++])) // left-to-right
		while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
			ans.pop_back();
	if( ans.size() == p.size() )
		return ans;
	for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left
		while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
			ans.pop_back();
	ans.pop_back();
	return ans;
}