Cod sursa(job #480475)

Utilizator ilie.danilaIlie Teodor Danila ilie.danila Data 28 august 2010 00:45:02
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

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;
	int index;
	vector<point> crescator;
	vector<point> descrescator;
	vector<point>::iterator iter;

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

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

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

	descrescator.resize(crescator.size());
	reverse_copy(crescator.begin(), crescator.end(), descrescator.begin());

	for( iter = descrescator.begin() + 1; iter != descrescator.end(); iter++ )
	{
		crescator.push_back( *iter );
	}

	index = 1;

	do
	{
		iter = crescator.begin() + index;
		double a = crescator[index - 1].y - crescator[index + 1].y;
		double b = crescator[index + 1].x - crescator[index - 1].x;
		double c = crescator[index + 1].y * crescator[index - 1].x -
				   crescator[index + 1].x * crescator[index - 1].y;

		long double ecuatie = a * crescator[index].x +
							  b * crescator[index].y +
							  c;
		if( ecuatie > 0 )
		{
			crescator.erase( iter );
			if( index > 1 )
			{
				index--;
			}
		}
		else if( index < crescator.size() - 1 )
			{
				index++;
			}

	}while( index < crescator.size() - 1 );

	crescator.pop_back();

	fout << crescator.size() << "\n";

	for( iter = crescator.begin(); iter != crescator.end(); iter++ )
	{
		fout << (*iter).x << " " << (*iter).y << "\n";
	}

	fout.close();

	return 0;
}