Cod sursa(job #410309)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 4 martie 2010 11:39:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "infasuratoare.in"
#define file_out "infasuratoare.out"

#define Nmax 122121

int poz;
double x[Nmax];
double y[Nmax];
int n,i,k,st[Nmax],a[Nmax];

int cmp(int i, int j)
{
	return (x[i]-x[poz])*(y[j]-y[poz])<(y[i]-y[poz])*(x[j]-x[poz]);
}

double aria(int a, int b, int c)
{
	return (x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-y[b]*x[c]-x[a]*y[c]-y[a]*x[b]);
}

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=1;i<=n;++i)
		 scanf("%lf %lf", &x[i], &y[i]);
	
	//caut cel mai din stanga punct, iar in caz de egalitate cel mai de jos
	poz=0;
	x[poz]=10000000.0;
	y[poz]=10000000.0;
	
	for (i=1;i<=n;++i)
		 if ((x[i]<x[poz]) || (x[i]==x[poz] && y[i]<y[poz]))
			 poz=i;
		 
	
	for (i=1;i<=n;++i)
         if (i!=poz)
			 a[++a[0]]=i;
		 
	//sortez in functie de panta dreptei
	sort(a+1,a+a[0]+1,cmp);	 
	k=0;	 
	st[++k]=poz;
	st[++k]=a[0];
	for (i=1;i<=a[0];++i)
	{
		while(k>1 && aria(st[k-1],st[k],a[i])>0) k--;
		st[++k]=a[i];
	}
	
	printf("%d\n", k);
	
	for(i=k;i>=1;--i)
		 printf("%.6lf %.6lf\n", x[st[i]],y[st[i]]);

	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}