Cod sursa(job #480182)

Utilizator ilie.danilaIlie Teodor Danila ilie.danila Data 26 august 2010 18:41:01
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct point
{
	double x;
	double y;
};

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

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

	int n;
	vector<point> puncte;

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

		puncte.push_back(punct);
	}

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

	fin.close();

	vector<point> infasuratoare;

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

//	fout << puncte[0].x << " " << puncte[0].y << " added\n";
//	fout << puncte[1].x << " " << puncte[1].y << " added\n";

	for( int i = 2; i < n; i++ )
	{
		double ecuatie, a, b, c;

		do
		{
			int index = infasuratoare.size() - 1;

			a = infasuratoare[index - 1].y - infasuratoare[index].y;
			b = infasuratoare[index].x - infasuratoare[index - 1].x;
			c = infasuratoare[index].x * infasuratoare[index - 1].y -
					infasuratoare[index].y * infasuratoare[index - 1].x;

			ecuatie = a * puncte[i].x + b * puncte[i].y + c;

			if( ecuatie > 0 )
			{
//				fout << infasuratoare[index].x << " " << infasuratoare[index].y << " removed\n";
				infasuratoare.pop_back();
			}
		}while( ecuatie > 0 );

//		fout << puncte[i].x << " " << puncte[i].y << " added\n";
		infasuratoare.push_back( puncte[i] );
	}

	for( int i = n - 2; i >= 0; i-- )
	{
		double ecuatie, a, b, c;

		do
		{
			int index = infasuratoare.size() - 1;

			a = infasuratoare[index - 1].y - infasuratoare[index].y;
			b = infasuratoare[index].x - infasuratoare[index - 1].x;
			c = infasuratoare[index].x * infasuratoare[index - 1].y -
					infasuratoare[index].y * infasuratoare[index - 1].x;

			ecuatie = a * puncte[i].x + b * puncte[i].y + c;

			if( ecuatie < 0 )
			{
//				fout << infasuratoare[index].x << " " << infasuratoare[index].y << " removed\n";
				infasuratoare.pop_back();
			}
		}while( ecuatie < 0 );

//		fout << puncte[i].x << " " << puncte[i].y << " added\n";
		infasuratoare.push_back( puncte[i] );
	}

	fout << infasuratoare.size() - 1 << "\n";

	for( int i = infasuratoare.size() - 1; i > 0; i-- )
		fout << infasuratoare[i].x << " " << infasuratoare[i].y << "\n";

	fout.close();

	return 0;
}