Cod sursa(job #481838)

Utilizator ilie.danilaIlie Teodor Danila ilie.danila Data 1 septembrie 2010 19:44:00
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

struct point
{
	double x;
	double y;
};

bool comparison( const point& A, const point& B )
{
	if( A.y < B.y || ( A.y == B.y && A.x > B.x ) )
		return true;
	else
		return false;
}

bool turnsRight( const point& A, const point& B, const point& C )
{
	double a = A.y - B.y;
	double b = B.x - A.x;
	double c = A.x * B.y - B.x * A.y;

	double ecuation = a * C.x + b * C.y + c;
	
	return ( ecuation < 0 );
}

int main()
{
	ifstream fin("infasuratoare.in");
	ofstream fout("infasuratoare.out");

	vector<point> puncte;
	vector<point>::iterator iter;
	int n;

	fin >> n;

	for( int i = 0; i < n; i++ )
	{
		point punct;
		fin >> punct.x >> punct.y;

		puncte.push_back( punct );
	}
	fin.close();

	sort( puncte.begin(), puncte.end(), comparison );

	vector<point> stiva;

	stiva.push_back( puncte[0] );
	stiva.push_back( puncte[1] );

	for( int i = 2; i < puncte.size(); i++ )
	{
		while( stiva.size() > 1 && turnsRight( stiva[stiva.size() - 2], stiva[stiva.size() - 1], puncte[i] ))
			stiva.pop_back();

		stiva.push_back( puncte[i] );
	}

	for( int i = puncte.size() - 2; i >= 0 ; i-- )
	{
		while( stiva.size() > 1 && turnsRight( stiva[stiva.size() - 2], stiva[stiva.size() - 1], puncte[i] ))
			stiva.pop_back();

		stiva.push_back( puncte[i] );
	}

	stiva.pop_back();
	
	fout << stiva.size() << "\n";

	for( int i = 0; i < stiva.size(); i++ )
	{
		fout << stiva[i].x << " " << stiva[i].y << "\n";
	}

	return 0;
}