Cod sursa(job #709653)

Utilizator fhandreiAndrei Hareza fhandrei Data 8 martie 2012 12:55:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
//Include
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

//Definitii
#define x first
#define y second

//Constante
const int MAX_SIZE = 120001;

//Functii
template<class T>
T determinant(pair<T,T> a, pair<T,T> b, pair<T,T> c);

template<class T>
bool compara(pair<T,T> a, pair<T,T> b);

//Variabile
FILE *in, *out;

int nrPuncte;

pair<double, double> start, curent;
pair<double, double> puncte[MAX_SIZE];

vector<pair<double, double> > infasuratoare;
vector<pair<double, double> >::iterator it, end;

//Clase
class dupaUnghi
{
	public:
	bool operator () (pair<double, double> a, pair<double, double> b)
	{	return determinant(start, a, b) > 0;	}
};

//Main
int main()
{
	in = fopen("infasuratoare.in","rt");
	out = fopen("infasuratoare.out","wt");
	fscanf(in, "%d", &nrPuncte);
	
	fscanf(in, "%lf%lf", &start.x, &start.y);
	
	for(int i=1 ; i<nrPuncte ; ++i)
	{
		fscanf(in, "%lf%lf", &curent.x, &curent.y);
		
		//if(curent < start)
		if(compara(curent, start))
		{
			puncte[i] = start;
			start = curent;
		}
		else
			puncte[i] = curent;
	}
	
	puncte[0] = start;
	
	sort(puncte+1, puncte+nrPuncte, dupaUnghi());
	
	infasuratoare.reserve(nrPuncte);
	
	infasuratoare.push_back(start);
	infasuratoare.push_back(puncte[1]);
	
	for(int i=2 ; i<nrPuncte ; ++i)
	{
		while(determinant(infasuratoare[infasuratoare.size()-2], infasuratoare[infasuratoare.size()-1], puncte[i]) < 0)
			infasuratoare.pop_back();
		infasuratoare.push_back(puncte[i]);
	}
	
	fprintf(out, "%d", infasuratoare.size());
	
	end = infasuratoare.end();
	for(it=infasuratoare.begin() ; it!=end ; ++it)
		fprintf(out, "\n%lf %lf", it->x, it->y);
	
	
	
	
	fclose(in);
	fclose(out);
	return 0;
}

template<class T>
T determinant(pair<T,T> a, pair<T,T> b, pair<T,T> c)
{	return (a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x);	}

template<class T>
bool compara(pair<T,T> a, pair<T,T> b)
{
	if(a.y == b.y)
		return a.x < b.x;
	return a.y < b.y;
}