Cod sursa(job #450887)

Utilizator darrenRares Buhai darren Data 8 mai 2010 15:41:15
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include<cmath>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<stack>
using namespace std;

#define elif else if
const double eps = 0.0000000000001;

struct point
{
	double x, y;
};

int n, pmin;
point p[120001];
double minx = 120001, miny = 120001;
stack<int> st;

void read();
void write();
void scan();
double angle( point a )
{
	double xi, yi;
	xi = a.x - minx;
	yi = a.y - miny;
	if ( fabs( xi ) < eps )
		return 90;
	if ( xi > 0 )
		return atan( yi / xi );
	else
		return 180 + atan( yi / xi );
}
double dist_2( point a )
{
	double xi, yi;
	xi = a.x - minx;
	yi = a.y - miny;
	return xi * xi + yi * yi;
}
bool cond( const point& a, const point b )
{
	if ( fabs( angle( a ) - angle( b ) ) > eps )
		return angle( a ) < angle( b );
	return dist_2( a ) - dist_2( b ) > eps;
}
bool change( point x )
{
	//imi iau ultimele doua din stack
	point top = p[st.top()];
	int ax = st.top();
	st.pop();
	point pen = p[st.top()];
	st.push( ax );
	//----
	double x1, y1, x2, y2;
	x1 = top.x - pen.x;
	y1 = top.y - pen.y;
	x2 = x.x - pen.x;
	y2 = x.y - pen.y;
	if( x1 * y2 - x2 * y1 <= 0 )
        return 1;
    return 0;
}

int main()
{
	read();
	scan();
	write();
	return 0;
}

void read()
{
	ifstream fin( "infasuratoare.in" );
	fin >> n;
	for ( int i = 0; i < n; ++i )
	{
		fin >> p[i].x >> p[i].y;
		if ( p[i].y < miny )
		{
			pmin = i;
			minx = p[i].x;
			miny = p[i].y;
		}
		elif ( ( p[i].y - miny < eps ) && p[i].x < minx )
		{
			pmin = i;
			minx = p[i].x;
		}
	}
	point aux = p[pmin];
	p[pmin] = p[0];
	p[0] = aux;
	
	fin.close();
}

void write()
{
	ofstream fout( "infasuratoare.out" );
	fout << st.size() << '\n';
	stack<int> aux;
	while ( st.size() )
	{
		aux.push( st.top() );
		st.pop();
	}
	while ( aux.size() )
	{
		fout << fixed << setprecision( 6 ) << p[aux.top()].x << ' ' << p[aux.top()].y << '\n';
		aux.pop();
	}
	fout.close();
}

void scan()
{
	sort( p + 1, p + n, cond );
	st.push( 0 );
	st.push( 1 );
	st.push( 2 );
	for ( int i = 3; i < n; ++i )
	{
		while ( change( p[i] ) )
		{
			st.pop();
			if ( st.size() == 1 )
				break;
		}
		st.push( i );
	}
}