Cod sursa(job #702745)

Utilizator arch_enemyAngela Gossow arch_enemy Data 2 martie 2012 08:57:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define NMAX 120001
#define x first
#define y second
#define PDD pair< double, double >

int N, i, sens, Lg;
int Stiva[NMAX];
bool Used[NMAX];
PDD P[NMAX];

inline bool Semn( PDD A, PDD B, PDD C )
{
	double ecA = A.y - B.y, ecB = B.x - A.x, ecC = A.x*B.y - A.y*B.x;
	return ( ecA*C.x + ecB*C.y + ecC < 0 );
}

int main()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	
	scanf("%d", &N );
	for( i = 1; i <= N; ++i )
		scanf("%lf%lf", &P[i].x, &P[i].y );
	sort( P + 1, P + N+1 );
	
	memset( Used, false, sizeof(Used) );
	Stiva[1] = 1, Stiva[2] = 2, Used[2] = true;
	Lg = 2, i = 3, sens = 1;
	
	while( !Used[1] )
	{
		while( Used[i] )
		{
			if( i == N ) sens = -1;
			i += sens;
		}
		
		while( Lg > 1 && Semn( P[ Stiva[Lg-1] ], P[ Stiva[Lg] ], P[i] ) )
			Used[ Stiva[Lg--] ] = false;
		Used[i] = true, Stiva[++Lg] = i;
	}
	
	printf("%d\n", Lg - 1 );
	for( i = 1; i < Lg; ++i )
		printf("%.6lf %.6lf\n", P[ Stiva[i] ].x, P[ Stiva[i] ].y );
	
	return 0;
}