Cod sursa(job #412964)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 7 martie 2010 10:31:34
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include<algorithm>
using namespace std;
#include<vector>

#define pb push_back
#define mp make_pair
#define x first
#define y second

vector <pair <double,double> > c1,c2,c3,c4,c,sol,c5,c6;
double aux1,aux2;
int n;

void show2 ()
{
	int i;
	for(i=0;i<(int)c.size ();++i)
		printf("%lf %lf\n",c[i].x,c[i].y);
	printf("\n");
}
void show ()
{
	int i;
	printf("%d\n",sol.size ());
	printf("%lf %lf\n",sol[sol.size ()-1].x,sol[sol.size ()-1].y);
	for(i=0;i<(int)sol.size ()-1;++i)
		printf("%lf %lf\n",sol[i].x,sol[i].y);
	printf("\n");
}
void read ()
{
	double nr1,nr2;
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%lf %lf",&nr1,&nr2);
		if(nr1==0)
		{
			if(nr2>=0)
				c5.pb (mp (nr1,nr2));
			else
				c6.pb (mp (nr1,nr2));
		}
		if(nr1>0 && nr2>=0)
			c1.pb (mp (nr1,nr2));
		else if(nr1<0 && nr2>=0)
			c2.pb (mp (nr1,nr2));
		else if(nr1<0 && nr2<=0)
			c3.pb (mp (nr1,nr2));
		else if(nr1>0 && nr2<=0)
			c4.pb (mp (nr1,nr2));
	}
}

struct cmp 
{
	bool operator () (const pair<double,double> &a,const pair<double,double> &b) const
	{
		return (a.y/a.x)<(b.y/b.x); 
	}
};
struct cmp2 
{
	bool operator () (const pair<double,double> &a,const pair<double,double> &b) const
	{
		return (a.y<b.y); 
	}
};

void solve ()
{
	int i;
	for(i=0;i<(int)c1.size ();++i)
		c.pb (mp (c1[i].x,c1[i].y));
		
	for(i=c5.size ()-1;i>=0;--i)
		c.pb (mp (c5[i].x,c5[i].y));
	
	for(i=0;i<(int)c2.size ();++i)
		c.pb (mp (c2[i].x,c2[i].y));
	
	for(i=0;i<(int)c3.size ();++i)
		c.pb (mp (c3[i].x,c3[i].y));
	
	for(i=0;i<(int)c6.size ();++i)
		c.pb (mp (c6[i].x,c6[i].y));
	
	for(i=0;i<(int)c4.size ();++i)
		c.pb (mp (c4[i].x,c4[i].y));
	
	c.pb (mp (c[0].x,c[0].y));
	
	int p1=0,p2=1,rdy=0;
	for(i=2;i<(int)c.size ();++i)
	{
		if(((c[p1].x*c[p2].y)+(c[p2].x*c[i].y)+(c[i].x*c[p1].y)-(c[i].x*c[p2].y)-(c[p2].x*c[p1].y)-(c[p1].x*c[i].y))<=0)
			p2=i;
		else
		{
			sol.pb (mp (c[p2].x,c[p2].y));
			p1=p2;
			p2=i;
		}
		if(!rdy)
		{
			c.pb (mp (sol[0].x,sol[0].y));
			rdy=1;
		}
	}
}
int main ()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	aux1=-1,aux2=1;
	read ();
	sort(c1.begin (),c1.end (),cmp ());
	sort(c2.begin (),c2.end (),cmp ());
	sort(c3.begin (),c3.end (),cmp ());
	sort(c4.begin (),c4.end (),cmp ());
	sort(c5.begin (),c5.end (),cmp2 ());
	sort(c6.begin (),c6.end (),cmp2 ());
	solve ();
	show ();
	//show2  ();
	return 0;
}