Cod sursa(job #404999)

Utilizator alexeiIacob Radu alexei Data 27 februarie 2010 10:12:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<stdio.h>
#include<deque>
#include<algorithm>
using namespace std;

#define inf 1000000001
#define NMAX 120000

double PX=inf,PY=inf;
int ind=-1;
	
double X[NMAX],Y[NMAX];
int I[NMAX],D[NMAX];

inline bool cmp( int p1, int p2 )
{
	return (double)( X[p1]-PX )*( Y[p2]-PY )<(double)( Y[p1]-PY )*( X[p2]-PX );
}

inline bool semn( int p1, int p2, int p3 )
{
	return (double)( X[p1]-X[p3] )*( Y[p2]-Y[p3] )<(double)( Y[p1]-Y[p3] )*( X[p2]-X[p3] );
}
	
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	int N;
	scanf("%d",&N);
	
	int i;
	double a1,a2;
	for( i=1; i<=N; ++i )
	{
		scanf("%lf %lf",&a1,&a2);
		
		X[i]=a1,Y[i]=a2;
		if( PX>a1 || ( PX==a1 && PY>a2 ) )
		{
			PX=a1, PY=a2, ind=i;
		}
		
	}

	for(i=1; i<=N; ++i)
	{
		if( i==ind ) continue;
		else
			I[ ++I[0] ]=i;
	}
	
	sort( I+1, I+I[0]+1, cmp );
	
	int sf=1;
	D[sf]=ind;
	
	for(i=1; i<=I[0]; ++i)
	{
		while( sf>=2 && !semn( D[sf-1], D[sf], I[i] ) ) --sf;
		D[++sf]=I[i];
	}
	
	printf("%d\n",sf);
	
	for(i=sf; i>0; --i)
	{
		printf("%lf %lf\n",X[ D[i] ], Y[ D[i] ]);
	}

	return 0;
}