Cod sursa(job #360484)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 31 octombrie 2009 17:47:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 120001
int n,ind[N],st[N],p;
double x[N],y[N];
bool compar(const int&a,const int&b)
{
	return (double)(x[a]-x[p])*(y[b]-y[p])<(double)(x[b]-x[p])*(y[a]-y[p]);
}
void citire()
{
	scanf("%d",&n);
	scanf("%lf%lf",&x[1],&y[1]);
	p=1;
	for(int i=2; i<=n; ++i)
	{
		scanf("%lf%lf",&x[i],&y[i]);
		if(x[i]<x[p]||(x[i]==x[p]&&y[i]<y[p]))
			p=i;
	}
	for(int i=1; i<=n; ++i)
	{
		if(i==p)
			continue;
		ind[++ind[0]]=i;
	}
}
double sens(int a,int b,int c)
{
	return (double)x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-y[a]*x[b]-y[b]*x[c]-y[c]*x[a];
}
void infasuratoare()
{
	st[++st[0]]=p;
	for (int i=1; i<n; ++i)
	{
		//if (ind[i]==p)continue;
		while (st[0]-1&&sens(st[st[0]-1],st[st[0]],ind[i])>0)
			--st[0];
		st[++st[0]]=ind[i];
	}
}
void afis()
{
	printf("%d\n",st[0]);
	reverse(st+1,st+1+st[0]);
	for (int i=1; i<=st[0]; ++i)
		printf("%lf %lf\n",x[st[i]],y[st[i]]);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	citire();
	sort(ind+1,ind+1+ind[0],compar);
	infasuratoare();
	afis();
	return 0;
}