Cod sursa(job #600601)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 2 iulie 2011 16:19:48
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

struct punct
{
	double x,y;
};

punct a[120001];
int s[250000],n,lung,lung2,ss[250000];


bool cmp(punct a, punct b)
{
	return a.x<b.x;
}


void scoate(int k)
{
	while((a[k].y-a[s[lung]].y)*(a[k].x-a[s[lung-1]].x)>(a[k].x-a[s[lung]].x)*(a[k].y-a[s[lung-1]].y))
		--lung;
}
void adauga(int k)
{
	s[++lung]=k;
}

int main()
{
	int i;
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%lf%lf",&a[i].x,&a[i].y);
	sort(a+1,a+n+1,cmp);
	s[++lung]=1;
	s[++lung]=2;
	lung=2;
	for(i=3;i<=n;++i)
	{
		scoate(i);
		adauga(i);
	}
	for(i=1;i<lung;++i)
		ss[i]=s[i];
	lung2=lung;
	lung = 0;
	s[++lung]=n;
	s[++lung]=n-1;
	for(i=n-2;i>=1;--i)
	{
		scoate(i);
		adauga(i);
	}
	printf("%d\n",lung+lung2-2);
	for(i=1;i<lung2;++i)
		printf("%.6lf %.6lf\n",a[ss[i]].x,a[ss[i]].y);
	for(i=1;i<lung;++i)
		printf("%.6lf %.6lf\n",a[s[i]].x,a[s[i]].y);
}