23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // Convex Hull -- Gift Wrapping
23dfcca431 2011-02-23        kinaba: //   O(N log N)
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // ToDo : Rewrite by CCW...
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: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: bool byY( CMP a, CMP b )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	if( a.imag() == b.imag() )
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: bool byArg( CMP a, CMP b )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	return arg(a) < arg(b);
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: bool isRight( CMP a, CMP b, CMP c )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	return arg((c-b) / (b-a)) < 0;
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: 	vector<CMP>::iterator it = min_element( p.begin(), p.end(), byY );
23dfcca431 2011-02-23        kinaba: 	CMP o = *it;
23dfcca431 2011-02-23        kinaba: 	p.erase(it);
23dfcca431 2011-02-23        kinaba: 	for(int i=0; i<p.size(); ++i)
23dfcca431 2011-02-23        kinaba: 		p[i] -= o;
23dfcca431 2011-02-23        kinaba: 	sort( p.begin(), p.end(), byArg );
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	vector<CMP> q;
23dfcca431 2011-02-23        kinaba: 	q.push_back( CMP(0,0) );
23dfcca431 2011-02-23        kinaba: 	q.push_back( p[0] );
23dfcca431 2011-02-23        kinaba: 	for(int i=1; i<p.size(); ++i) {
23dfcca431 2011-02-23        kinaba: 		while( isRight(q[q.size()-2], q[q.size()-1], p[i]) )
23dfcca431 2011-02-23        kinaba: 			q.pop_back();
23dfcca431 2011-02-23        kinaba: 		q.push_back( p[i] );
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 	for(int i=0; i<q.size(); ++i)
23dfcca431 2011-02-23        kinaba: 		q[i] += o;
23dfcca431 2011-02-23        kinaba: 	return q;
23dfcca431 2011-02-23        kinaba: }