Cod sursa(job #810401)

Utilizator MtkMarianHagrSnaf MtkMarian Data 10 noiembrie 2012 11:26:45
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 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 120005

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 = 2;
	int i = 3 ;
	p = 1 ;
	st[ 1 ] = 1;	
	st[ 2 ] = 2;

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

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



}

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

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



	return 0;
}