Cod sursa(job #406189)

Utilizator bog29Antohi Bogdan bog29 Data 1 martie 2010 12:15:16
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<fstream>
#include<stack>
#include<math.h>
#define dmax 120005
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

long long n,p0,crt;
long double ymin,xmin,q,nr,pi=3.141592;

struct punct
{	long double x;
	long double y;
	long double up;
}	p[dmax];

stack<long long>st;	

typedef int (*compfn)(const void *,const void *);

int sf(struct punct *a,struct punct *b)
{	if(a->up > b->up)
		return 1;
	else if(a->up < b->up)
		return -1;
	return 0;
}

long double unghi(long long p2,long long p1)
{	return atan( ( p[p2].y-p[p1].y)/(p[p2].x-p[p1].x)) ;
}

long double prod_i(long long a,long long b,long long c)
{	long double p1,p2;
	p1=(p[a].x - p[c].x)*(p[b].y - p[c].y);
	p2=(p[b].x - p[c].x)*(p[a].y - p[c].y);
	return ( p1 - p2 );
}

int main()
{	long long i;
	in>>n;
	for(i=0;i<n;i++)
		in>>p[i].x>>p[i].y;
	in.close();
	ymin=-1000000000;
	xmin=-1000000000;
	for(i=0;i<n;i++)
	{	if(p[i].y < ymin || ymin==-1000000000)
		{	ymin=p[i].y;
			xmin=p[i].x;
			p0=i;
		}
		if(p[i].y==ymin)
			if(p[i].x<xmin)	
				p0=i;
	}
	for(i=0;i<n;i++)
		if(i!=p0)
		{	p[i].up=unghi(i,p0);
			if(p[i].up <=0) p[i].up=pi+p[i].up;
		}	
	qsort((void*)&p,n,sizeof(struct punct),(compfn)sf);
	st.push(0);
	st.push(1);
	st.push(2);
	for(i=3;i<n;i++)
	{	while(prod_i (i, st.top(), *(&st.top()-1) ) >=0 )
			st.pop();	
		st.push(i);
	}
	out<<st.size()<<'\n';
	for(i=st.size()-1;i>=0;i--)
	{	crt=*(&st.top()-i);
		out<<fixed<<p[crt].x<<" "<<p[crt].y<<'\n';
	}	
	out.close();
	return 0;
}