Cod sursa(job #659147)

Utilizator cristicecCristian Uricec cristicec Data 10 ianuarie 2012 11:26:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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(lung>=2 && (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);

return 0;
}