Cod sursa(job #810329)

Utilizator MtkMarianHagrSnaf MtkMarian Data 10 noiembrie 2012 09:50:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<cstdio>
#include<algorithm>
#include<vector>



using namespace std ;

#define PDD pair<double , double >
#define f  first
#define s second 
#define mk make_pair

#define NMAX 120000

vector< PDD > pct ;

int n ,p ,  k ,viz[NMAX]={0},st[NMAX];
double x , y ;
int semn( PDD a, PDD b, PDD c )
{
	double cx = b.s-a.s ;
	double cy = a.f-b.f ; 
	double cz = b.first * a.second - a.first * b.second ;

	if( cx*c.f + cy*c.s+cz < 0  ) return -1 ;
	else return 1 ;
	

}
inline int cmp(PDD a , PDD b )
{
	if( a.f < b.f) return 1 ;
	else
		if( a.f > b.f) return 0 ;
		else
			if(a.s <= b.s) return 1 ;
			else return 0;


}
void citeste()
{
	scanf("%d",&n);
	for ( int i = 1; i <= n ; ++i )
	{
		scanf("%lf",&x);
		scanf("%lf",&y);
		
		pct.push_back ( mk ( x , y ) );

	}

}

void infasuratoarea()
{
	k = 1;
	int i = 2 ;
	p = 1 ;
	st[ 0 ] = 0;	
	st[ 1 ] = 1;

	viz[ 1 ] = 1;
	while( !viz[ 0 ] )
	{
		while(viz [ i ] )
		{
			if( i == (n-1) ) p = -1 ;
			i += p;
		}

		while( k >= 1 &&   semn(  pct [ st [ k-1 ] ] , pct[ st [ k ] ] , pct[ i ]   )   == -1 )		
			viz[ st[ k--  ]] = 0;
		
		
		viz[ i ] = 1 ; 
		st[ ++k ] = i ;
	}



}

void afisare()
{
	printf("%d\n",k);

	
	for(int i = k ; i > 0 ; --i )  
	{
			printf("%lf %lf\n" , pct[ st[i] ].f,pct[ st[i] ].s );
	}
}
int main()
{
	freopen("infasuratoarea.in","r",stdin);
	freopen("infasuratoarea.out","w",stdout);

	citeste();

	sort(pct.begin() , pct.end(),cmp);

	
	infasuratoarea();
	afisare();



	return 0;
}