Cod sursa(job #969195)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 3 iulie 2013 19:40:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>

typedef std::pair<double,double> Point;
typedef std::vector<Point> Polygon;

const int MAX_SIZE(120001);

Polygon Hull;
std::vector<Point> Points;
Point Stack [MAX_SIZE];

inline void Read (void)
{
	std::freopen("infasuratoare.in","r",stdin);
	double x, y;
	int n;
	std::scanf("%d",&n);
	for (int counter(0) ; counter < n ; ++counter)
	{
		std::scanf("%lf %lf",&x,&y);
		Points.push_back(std::make_pair(x,y));
	}
	std::fclose(stdin);
}

inline void Print (void)
{
	std::freopen("infasuratoare.out","w",stdout);
	std::printf("%lu\n",Hull.size());
	for (int index(0), end(Hull.size()) ; index < end ; ++index)
		std::printf("%.9lf %.9lf\n",Hull[index].first,Hull[index].second);
	std::fclose(stdout);
}

inline double Determinant (Point &a, Point &b, Point &c)
{
	return a.first * b.second - a.second * b.first + b.first * c.second - b.second * c.first + c.first * a.second - c.second * a.first;
}

inline void Andrew (void)
{
	std::sort(Points.begin(),Points.end());
	const int END(Points.size());
	Stack[0] = Points[0];
	Stack[1] = Points[1];
	int top(1), index;
	// Upper Hull
	for (index = 2 ; index < END ; ++index)
	{
		while (top >= 1 && Determinant(Stack[top - 1],Stack[top],Points[index]) > 0)
			--top;
		Stack[++top] = Points[index];
	}
	while (top >= 0)
	{
		Hull.push_back(Stack[top]);
		--top;
	}
	Stack[0] = Points[END - 1];
	Stack[1] = Points[END - 2];
	top = 1;
	// Lower Hull
	for (index = END - 3 ; index >= 0 ; --index)
	{
		while (top >= 1 && Determinant(Points[index],Stack[top],Stack[top - 1]) < 0)
			--top;
		Stack[++top] = Points[index];
	}
	--top;
	while (top >= 1)
	{
		Hull.push_back(Stack[top]);
		--top;
	}
}

int main (void)
{
	Read();
	Andrew();
	Print();
	return 0;
}