Cod sursa(job #718566)

Utilizator ioanabIoana Bica ioanab Data 20 martie 2012 21:29:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <algorithm>
using namespace std;

struct point
{
    double x,y;
};

point v[120005];
point s1[120005];
point s2[120005];


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

bool panta (point a,point b,point c)
{
	return (b.y-a.y)*(c.x-a.x)<(b.x-a.x)*(c.y-a.y);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	int n,i,k=0,p=0;
	scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf",&v[i].x);
		scanf("%lf",&v[i].y);
    }
    sort(&v[1],&v[n+1],cmp);
    s1[++k]=v[1];
    for(i=2;i<=n;i++)
    {
        while(panta(s1[k-1],s1[k],v[i])&& k>1)
		{
            k--;
		}
        s1[++k]=v[i];
    }
	k--;
	s2[++p]=v[n];
    for(i=n-1;i>=1;i--)
    {
       	while(panta(s2[p-1],s2[p],v[i]) && p>1)
		{
            p--;
		}
        s2[++p]=v[i];
    }
	p--;
	printf("%d\n",p+k);
    for(i=p;i>=1;i--)
        printf("%.6lf %.6lf\n",s2[i].x,s2[i].y);
	for(i=k;i>=1;i--)
		printf("%.6lf %.6lf\n",s1[i].x,s1[i].y);
	
    return 0;
}