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