Cod sursa(job #720808)

Utilizator valiro21Valentin Rosca valiro21 Data 22 martie 2012 22:07:31
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include <cstdio>
#include <algorithm>
#define NMax 120021
#include <list>
#include <cmath>
#define INFINIT 1000000001

using namespace std;

struct cord{
	double x,y,sin;
};

list<cord> li,lst;
cord ve[NMax];
long start,n,mini;
double minx,miny,dx1,dx2,dy1,dy2,x,y;

inline bool compare(cord p1,cord p2)
{
	if(p1.sin<p2.sin)
		return 1;
	else
		if(p1.sin==p2.sin)
			if(p1.y < p2.y)
				return 1;
			else
				if(p1.y == p2.y)
					if(p1.x < p2.x)
						return 1;

	return 0;
}

int inline right_turn(double dx1,double dy1,double dx2,double dy2,double px,double py)
{
	int semn=1;
	if(dx1>dx2)
		semn*=-1;

	if(dx2==dx1)
	{
		if(dy1>dy2)
			semn*=-1;
		if(px>dx1)
			return semn;
		else
			return -semn;
	}

	double a=(dy2-dy1)/(dx2-dx1);
	double b=dy1-a*dx1;
	long pya=a*px+b;

	if(semn==1)
	{
		if(py>=pya)
			return -semn;
		return semn;
	}
	else
	{
		if(py>pya)
			return -semn;
		return semn;
	}
}

void bck()
{
	lst.push_front(ve[1]);lst.push_front(ve[2]);
	cord u,p;

	for(long start=3;start<=n;start++)
	{
		u=lst.front();
		lst.pop_front();
		p=lst.front();
		lst.push_front(u);

 		if(right_turn(p.x,p.y,u.x,u.y,ve[start].x,ve[start].y)==-1)
			lst.push_front(ve[start]);
		else
		{
			while(right_turn(p.x,p.y,u.x,u.y,ve[start].x,ve[start].y)==1)
			{
				lst.pop_front();
				u=lst.front();
				lst.pop_front();
				p=lst.front();
				lst.push_front(u);
			}
			lst.push_front(ve[start]);
		}

	}

}

int main()
{
	freopen("infasuratoare.in","rt",stdin);
	freopen("infasuratoare.out","wt",stdout);
	
	scanf("%ld",&n);
	minx=miny=INFINIT;
	for(long i=1;i<=n;i++)
	{
		scanf("%lf %lf",&x,&y);
		ve[i].x=x;ve[i].y=y;
		if(y<miny)
			minx=x,miny=y,mini=i;
		else
			if(miny==y && x<minx)
				minx=x,mini=i;
	}

	for(long i=1;i<=n;i++)
	{
		if(ve[i].x-minx<0)
			ve[i].sin = 2-( ve[i].y - miny )/sqrt( ( ve[i].x-minx ) * ( ve[i].x-minx ) + ( ve[i].y-miny ) * ( ve[i].y-miny ) );
		else
			if(ve[i].x-minx>0)
				ve[i].sin=( ve[i].y - miny )/sqrt( ( ve[i].x-minx ) * ( ve[i].x-minx ) + ( ve[i].y-miny ) * ( ve[i].y-miny ) );
			else
				ve[i].sin=1;
	}

	cord aux=ve[mini];
	ve[mini]=ve[1];
	ve[1]=aux;

	sort(ve+2,ve+n+1,compare);
	
	bck();
	
	printf("%ld\n",lst.size());
	while(!lst.empty())
	{
		printf("%lf %lf\n",lst.back().x,lst.back().y);
		lst.pop_back();
	}
	
	return 0;
}