Cod sursa(job #296559)

Utilizator AndreyPAndrei Poenaru AndreyP Data 4 aprilie 2009 22:09:00
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#include<bitset>
#include<algorithm>
using namespace std;
#define pdd pair<double,double>
#define mp make_pair
#define x first
#define y second
#define N 120010
const double eps=1e-12;
int n,k;
pdd v[N];
int st[N];
bitset<N> uz;
inline char cmp(double a,double b)
{
	if(a+eps<b) 
		return -1;
	if(b+eps<a) 
		return 1;
    return 0;
}
inline char semn(pdd a,pdd b,pdd c)
{
	double A=a.y-b.y,B=b.x-a.x,C=a.x*b.y-b.x*a.y;
	return cmp(A*c.x+B*c.y+C,0);
}
bool compar(const pdd &a,const pdd &b)
{
	char aux=cmp(a.x,b.x);
	if(aux)
		return (aux==-1);
	return (cmp(a.y,b.y)==-1);
}
inline void citire()
{
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
		scanf("%lf%lf",&v[i].x,&v[i].y);
	sort(v+1,v+n+1,compar);
}
inline void rezolva()
{
	k=2;
	uz[2]=true;
	st[1]=1;
	st[2]=2;
	int i=3,pas=1;
	while(!uz[1])
	{
		while(uz[i])
		{
			if(i==n)
				pas=-1;
			i+=pas;
		}
		while(k>1 && semn(v[st[k-1]],v[st[k]],v[i])==-1)
			uz[st[k--]]=false;
		st[++k]=i;
		uz[i]=true;
	}
}
inline void scrie()
{
	printf("%d\n",k-1);
	for(int i=1; i<k; ++i)
		printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	citire();
	rezolva();
	scrie();
	return 0;
}