Artifact 9ffbc36d1d4aa6a7da03e785207383c67286dbcf
//-------------------------------------------------------------
// 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;
}