Cod sursa(job #779084)

Utilizator danalex97Dan H Alexandru danalex97 Data 16 august 2012 16:35:40
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

#define x first
#define y second

typedef pair<double,double> Pair;

const int Nmax = 120011 ;

int N,Size;
Pair A[Nmax];
int St[Nmax],Rez[Nmax];

#define EPS 1e-12

int Ecu ( Pair A , Pair B , Pair P )
{
	double a = A.y - B.y ; 
	double b = B.x - A.x ;
	double c = - A.y * B.x + B.y * A.x ;
	
	if ( a*P.x + b*P.y + c + EPS > 0 ) return 1;
	if ( a*P.x + b*P.y + c - EPS < 0 ) return -1;
	
	return 0;
}

void Solve(int i)
{
	St[++Size] = i;
	if ( Size > 2 )
		while ( Size > 2 ) 
		{
			if ( Ecu ( A[St[Size-2]] , A[St[Size]] , A[St[Size-1]] ) < 0 )
				St[Size-1]=St[Size],
				--Size,
				St[Size+1]=0;
			else
				break;
		}
}

void Andrew()
{
	sort(A+1,A+N+1);
	
	St[++Size] = 1;
	for (int i=2;i<N;++i)
		if ( Ecu ( A[N] , A[1] , A[i] ) < 0 )
			Solve( i );
	for (int i=1;i<=Size;++i)
		Rez[++Rez[0]]=St[i],
		St[i]=0;
	
	Size=0;	
	St[++Size] = N;
	for (int i=N-1;i>1;--i)
		if ( Ecu ( A[1] , A[N] , A[i] ) < 0 )
			Solve( i );
	for (int i=1;i<=Size;++i)
		Rez[++Rez[0]]=St[i],
		St[i]=0;
}

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

int main()
{
	F>>N;
	for (int i=1;i<=N;++i)
		F>>A[i].x>>A[i].y;
	
	Andrew();
	
	G<<Rez[0]<<'\n';
	for (int i=Rez[0];i;--i)
		G<<fixed<<setprecision(6)<<A[Rez[i]].x<<' '<<A[Rez[i]].y<<'\n';
}