Cod sursa(job #412962)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 7 martie 2010 10:14:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 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;
double aux1,aux2;
int n;

void show ()
{
	int i;
	printf("%d\n",sol.size ()-1);
	printf("%lf %lf\n",sol[sol.size ()-2].x,sol[sol.size ()-2].y);
	for(i=0;i<(int)sol.size ()-2;++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)
				aux1=max(aux1,nr2);
			else
				aux2=min(aux2,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); 
	}
};

void solve ()
{
	int i;
	for(i=0;i<(int)c1.size ();++i)
		c.pb (mp (c1[i].x,c1[i].y));
		
	if(aux1>=0)
		c.pb (mp (0,aux1));
	
	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));
	
	if(aux2<0)
		c.pb (mp (0,aux2));
	
	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;
	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(sol.size ()==1)
			c.pb (mp (sol[0].x,sol[0].y));
	}
}
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 ());
	solve ();
	show ();
	return 0;
}