Cod sursa(job #1010982)

Utilizator superman_01Avramescu Cristian superman_01 Data 16 octombrie 2013 00:01:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iomanip>

#define NMAX 120005
#define INF 0x3f3f3f3f

using namespace std;

ifstream in ( "infasuratoare.in" );
ofstream out ( "infasuratoare.out" );

pair < double , double > Points[NMAX];
int N;
int stack[NMAX] , k;
pair < double , double > MinPoint;

bool cmp ( pair < double , double > A , pair < double , double > B )
{
	if ( ( A.first - MinPoint.first) * (B.second - MinPoint.second) > ( A.second - MinPoint.second ) * ( B.first - MinPoint.first) )
		return true ;
	else
		return false;
}
double SignArea ( pair < double , double > A , pair < double , double > B , pair  < double , double > C )
{
	return ( B.first - A.first )* ( C.second - A.second ) - ( C.first - A.first ) * ( B.second - A.second) ;
}

int main ( void )
{
	int i ; 
	in >> N ; 
	int Ind;
	MinPoint.first = MinPoint.second = INF;
	for ( i = 1 ; i <= N ; ++i )
	{
		in >> Points[i].first >> Points[i].second;
		if( ( Points[i].second <  MinPoint.second ) ||  ( ( Points[i].second == MinPoint.second ) and ( Points[i].first < MinPoint.first )))
		{
			MinPoint = Points[i];
			Ind = i;
		}
	}
	swap( Points[1] , Points[Ind] );
	sort ( Points + 2  , Points  + N + 1 , cmp );
    stack[1] = 1 ; 
	stack[2] = 2 ;
	k = 2 ;
	for ( i = 3 ; i <= N ; ++i )
	{
		while ( k > 1 and SignArea ( Points[stack[k-1]] , Points[stack[k]] , Points[i] ) < 0)
			--k ;
		stack[++k] = i ;
	}
	out << k << "\n";
	out << fixed << setprecision(6);
	for ( i = 1 ; i <= k ; ++i )
		out << Points[stack[i]].first <<" "<< Points[stack[i]].second << "\n";
	return 0;
}