Cod sursa(job #450923)

Utilizator darrenRares Buhai darren Data 8 mai 2010 17:02:00
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
// Buhai Rares
// Infasuratoarea Convexa
// Scanarea Graham

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;

#define elif else if
const double eps = 0.00000000001;

struct point
{
	double x, y;
};

int n, pmin;
point p[120001];
double minx = 120001, miny = 120001;
int st[120001], nr = -1;

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 ) // Paralel cu oy
		return 90;
	if ( xi > 0 )
		return 180 * ( atan( yi / xi ) / M_PI ); // Tangenta este y / x
	else
		return 180 - fabs( 180 * ( atan( yi / xi ) / M_PI ) ); // Trebuie sa fie 180-, ( este in cealalta parte )
}
double dist_2( point a )
{
	double xi, yi;
	xi = a.x - minx;
	yi = a.y - miny;
	return xi * xi + yi * yi; // Pitagora^2
}
bool cond( const point& a, const point b )
{
	/*if ( fabs( angle( a ) - angle( b ) ) > eps ) // Unghiuri diferite => sortam dupa unghiul polar
		return angle( a ) < angle( b );
	return dist_2( a ) - dist_2( b ) > eps; // Unghiuri egale => sortam dupa raza polara*/
	return  ( b.x - minx ) * ( a.y - miny ) - ( a.x - minx ) * ( b.y - miny ) < 0;
}

bool change( point x )
{
	point top = p[st[nr]];
	point pen = p[st[nr - 1]];
	double a, b, c;
	a = pen.y - top.y;
	b = top.x - pen.x;
	c = pen.x * top.y - pen.y * top.x;
	
	if ( a * x.x + b * x.y + c < 0 ) // Verificam in ce semiplan este. Dreapta => pozitiv, stanga => negativ
		return 1;
    return 0;
}

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

void read()
{
	freopen( "infasuratoare.in", "r", stdin );
	scanf( "%d", &n );
	for ( int i = 0; i < n; ++i )
	{
		scanf( "%lf %lf", &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;
}

void write()
{
	freopen( "infasuratoare.out", "w", stdout );
	printf( "%d\n", nr + 1 );
	for ( int i = 0; i <= nr; ++i )
		printf( "%.10lf %.10lf\n", p[st[i]].x, p[st[i]].y );
}

void scan()
{
	sort( p + 1, p + n, cond );
	st[++nr] = 0;
	st[++nr] = 1;
	st[++nr] = 2;
	for ( int i = 3; i < n; ++i ) // O(n * not_ok )
	{
		while ( change( p[i] ) )
		{
			--nr;
			if ( nr == 0 )
				break;
		}
		
		st[++nr] = i;
	}
}