Cod sursa(job #672772)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 3 februarie 2012 02:52:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
# include <cstdio>
# include <algorithm>
# include <fstream>

# define dim 120005
# define INF 999999999

using namespace std;

ifstream f("infasuratoare.in");

int i , n , k , s[ dim ] , poz;

struct punct 
{
	double x ,y,panta;
};
punct v[ dim ], o , aux;

inline int cmp ( punct a, punct b)
{
	if ( a.panta == b.panta ) 
		return a.x < b.x ;
	return a.panta < b.panta;
}

 int convex()
{
	punct a ,b , c;
	double S;
	
	a = v[ s[ k - 1 ] ];
	b = v[ s[ k ] ];
	c = v[ i ];
	
	S = ( a.x - c.x ) * ( b.y - a.y ) + ( a.x - b.x ) * ( a.y - c.y ) ;
	
	if ( S > 0 )
		return 1;
	return 0;
}

inline void citire()
{
	f >> n;
	
	o.x = o.y = INF ;
	
	for ( i = 1 ; i <= n ; i++ )
	{
		f >> v[ i ].x >> v[ i ].y;
		
		if ( v[ i ].x < o.x || v[ i ].x == o.x && v[ i ].y < o.y )
			o = v[ i ],poz = i;
		
	}
}

inline void rezolva()
{
	aux = v[ 1 ];
	v[ 1 ] = v[ poz ];
	v[ poz ] = aux;
	
	for( i = 2 ; i <= n ; i++ )
		v[ i ].panta = ( v[ i ].y - o.y ) / ( v[ i ].x - o.x );
	
	sort( v + 2 , v + n + 1 , cmp );
	
	s[ 1 ] = 1 ;
	s[ 2 ] = 2 ;
	k = 2 ;
	
	for( i = 3 ; i <= n ; i++ )
	{
		while ( convex() == 0 && k > 2 )
			k--;
		k++;
		s[ k ] = i;
	}
}

inline void afisare()
{
	freopen("infasuratoare.out","w",stdout);
	
	int i;

	printf("%d\n",k);
	
	for( i = 1 ; i <= k ; i++ )
		printf("%0.7lf %0.7lf\n",v[ s[ i ] ].x ,v[ s[ i ] ].y );
}

int main()
{
	citire();
	rezolva();
	afisare();
	return 0;
}