Cod sursa(job #1773189)

Utilizator dodecagondode cagon dodecagon Data 7 octombrie 2016 17:11:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <algorithm>


using namespace std;

struct punct 
{
	double x,y;
};

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

bool 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);
}


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



int main(int argc, char const *argv[])
{
	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);

	 sort(a,a+n,cmp);


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

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

    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;
}