Cod sursa(job #616131)

Utilizator BitOneSAlexandru BitOne Data 11 octombrie 2011 20:00:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <queue>
#include <vector>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 120011


using namespace std;
struct point
{
	double x, y;
	point() : x(0.00000000), y(0.00000000) {}
	point( double _x, double _y ) : x(_x), y(_y) {}
} p, p0( 1111111111.00000000, 1111111111.00000000 );
vector< point > v, S;
bool operator<( const point& A, const point& B ) { return (A.x-p0.x)*(B.y-p0.y) < (A.y-p0.y)*(B.x-p0.x); }
inline istream& operator>>( istream& in, point& A )
{
	in>>A.x>>A.y;
	return in;
}
inline ostream& operator<<( ostream& out, const point& A )
{
	out<<fixed<<setprecision(8)<<A.x<<' '<<A.y;
	return out;
}
inline bool det( const point& A, const point& B, const point& C )
{
	return  ( A.x*B.y+B.x*C.y+A.y*C.x ) >= ( A.y*B.x+B.y*C.x+A.x*C.y );
}
int main( void )
{
	int N, i, j;
	ifstream in("infasuratoare.in" );
	in>>N>>p0;
	for( i=1; i < N; ++i )
	{
		in>>p;
		if( p.x < p0.x || ( p.x == p0.x && p.y < p0.y ) )
			v.push_back( p0 ), p0=p;
		else v.push_back( p );
	}
	sort( v.begin(), v.end() );
	S.push_back( p0 );
	S.push_back( v[0] );
	S.push_back( v[1] );
	for( i=2, --N; i < N; ++i )
	{
		for( j=S.size()-1; j >= 1 && det( S[j-1], S[j], v[i] ); --j, S.pop_back() );
		S.push_back( v[i] );
	}
	ofstream out( "infasuratoare.out" );
	out<<S.size()<<'\n';
	copy( S.rbegin(), S.rend(), ostream_iterator<point>( out, "\n" ) );
	out<<'\n';
	return EXIT_SUCCESS;
}