Cod sursa(job #1226592)

Utilizator HotSteelBeteag Ion Andrei HotSteel Data 6 septembrie 2014 12:55:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

namespace math
{
	static const double eps = 1.e-12;
	static const double inf = 1.e9;

	template<class T>
	class POINT
	{
	private:
		T x, y;
	public:
		POINT() : x(0), y(0) {};
		POINT(T _x, T _y) : x(_x), y(_y) {};
		POINT(const POINT& other) : x(other.x), y(other.y) {};

		T getx() const
		{
		    return x;
        };

		T gety() const
		{
		    return y;
        };

		void setx(T _x)
		{
		    x = _x;
        };

		void sety(T _y)
		{
		    y = _y;
        };

		double distance(const POINT& other) const
		{
			return sqrt((x - other.x)*(x - other.x) + (y - other.y)*(y - other.y));
		}

		POINT middle(const POINT& other) const
		{
			return POINT((x + other.x) / 2, (y + other.y) / 2);
		}

		bool operator == (const POINT& other) const
		{
			return (fabs(x - other.x) < eps && fabs(y - other.y) < eps);
		}

		double cp(const POINT& b, const POINT& c) const
		{
			return (b.x - x) * (c.y - b.y) - (b.y - y) * (c.x - b.x);
		}

		int ccw(const POINT& b, const POINT& c) const
		{
			if(cp(b,c) < 0)
				return -1;

			if(cp(b,c) > 0)
				return 1;

			return 0;
		}
	};
}

using namespace math;

vector< POINT<double> > p;
int st[120005];
int top;

bool cmp(const POINT<double>& a,const POINT<double>& b)
{
	if (p[0].ccw(a,b) > 0)
		return true;

	return false;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

	double tx,ty;
	int n,i;

	scanf("%d",&n);
	scanf("%lf%lf",&tx,&ty);
	p.push_back(POINT<double>(tx,ty));
	for(i=1;i<n;++i)
	{
		scanf("%lf%lf",&(tx),&(ty));
		p.push_back(POINT<double>(tx,ty));

		if( ((fabs(p[i].gety() - p[0].gety()) < eps) && p[i].getx() - p[0].getx() <= -eps) || ((p[i].gety() - p[0].gety()) <= -eps) )
			swap(p[0],p[i]);
	}
	sort(p.begin()+1,p.end(),cmp);
	p.push_back(*(p.begin()));
	st[0] = 0;
	st[1] = 1;
	top = 1;
	i = 2;

	while(i <= n)
	{
		if(p[st[top-1]].ccw(p[st[top]],p[i]) > 0)
			{
				st[++top] = i;
				++i;
			}
		else
			--top;
	}

	printf("%d\n",top);
	for(i=0;i<top;++i)
	{
		printf("%lf %lf\n",p[st[i]].getx(),p[st[i]].gety());
	}

    return 0;
}