Cod sursa(job #1773325)

Utilizator dodecagondode cagon dodecagon Data 7 octombrie 2016 18:53:02
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

struct punct 
{
	double x,y;
};

punct a[120009];
int st[120009],n,m,i,j,k,p=1;

int sgn(punct * a,punct * b,punct * c)
{
	return ((a->x*b->y+a->y*c->x+b->x*c->y-c->x*b->y-b->x*a->y-a->x*c->y) < 0);
}


int cmp(const punct &a,const punct & b)
{
	if (a.x==b.x)
		return (a.y>b.y);
	return (a.x<b.x);
}


int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);

	 scanf("%d",&n);
	 for (i=0;i<n;++i)
	 	scanf("%lf%lf",&a[i].x,&a[i].y);

	 //qsort(a,n,sizeof(punct),cmp);

	 sort(a,a+n,cmp);

	 k=1;
	 st[k]=0;
	 st[++k]=1;

	  for (i=2;i>=0;i+=p)
	  {
	    while (k>1 && sgn(&a[st[k-1]],&a[st[k]],&a[i]))
	    	 k--;
        st[++k]=i;
        if (i==n-1) p=-1;
	  }

	 
    printf("%d\n",k-1);

	 for (i=1;i<k;++i)
	 	printf("%.6lf %.6lf\n",a[st[i]].x,a[st[i]].y);

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