Artifact 9ffbc36d1d4aa6a7da03e785207383c67286dbcf

• File _lib/geo/convexHull_old.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_old.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

//-------------------------------------------------------------
// Convex Hull -- Gift Wrapping
//   O(N log N)
//
// ToDo : Rewrite by CCW...
//
// Verified by
//   - SRM 336 Div1 LV3
//-------------------------------------------------------------

bool byY( CMP a, CMP b )
{
	if( a.imag() == b.imag() )
		return a.real() < b.real();
	return a.imag() < b.imag();
}

bool byArg( CMP a, CMP b )
{
	return arg(a) < arg(b);
}

bool isRight( CMP a, CMP b, CMP c )
{
	return arg((c-b) / (b-a)) < 0;
}

vector<CMP> convex_hull( vector<CMP> p )
{
	vector<CMP>::iterator it = min_element( p.begin(), p.end(), byY );
	CMP o = *it;
	p.erase(it);
	for(int i=0; i<p.size(); ++i)
		p[i] -= o;
	sort( p.begin(), p.end(), byArg );

	vector<CMP> q;
	q.push_back( CMP(0,0) );
	q.push_back( p[0] );
	for(int i=1; i<p.size(); ++i) {
		while( isRight(q[q.size()-2], q[q.size()-1], p[i]) )
			q.pop_back();
		q.push_back( p[i] );
	}
	for(int i=0; i<q.size(); ++i)
		q[i] += o;
	return q;
}