Cod sursa(job #1741322)

Utilizator bogoismarandaBogoi Smaranda bogoismaranda Data 13 august 2016 17:35:06
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
# include<cstdio>
# include<algorithm>
# include<cmath>
# define eps 1.e-12
struct point { double x,y;};
point p[12000];
point ll;
int h[12000];
double cp( point p1,point p2,point p3)
{
	return(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int CCW(point p1,point p2,point p3)
{
	double ccp=cp(p1,p2,p3);
	if(fabs(ccp)<eps) return 0;
	if(ccp>=eps) return 1;
	return -1;
}
bool cmp(point p1,point p2)
{
    return CCW(p[0],p1,p2)>0;
}
int main ()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int top,i,n;
    double t1,t2;
    scanf("%d",&n);
    scanf("%lf%lf", &t1,&t2);
    p[0].x=t1;
    p[0].y=t2;
    ll=p[0];
    for(i=1;i<n;i++)
    {
            scanf("%lf%lf", &t1,&t2);
            p[i].x=t1;
            p[i].y=t2;
            if(p[i].y-ll.y<-eps || (fabs(p[i].y-ll.y <eps) && p[i].x-ll.x<-eps))
            {
                ll=p[i];
                p[i]=p[0];
                p[0]=ll;
            }

    }
    sort(p+1,p+n,cmp);
    p[n]=p[0];
    h[0]=0;h[1]=1;
    top=1;i=2;
    while(i<=n)
    {
        if(CCW(p[h[top-1]],p[h[top]],p[i])>0)
        {
            h[++top]=i;
            i++;
        }
        else top--;
    }
    printf("%d\n",top);
    for(i=0;i<top;i++)
        printf("%lf%lf\n",p[h[i]].x,p[h[i]].y);
    return 0;
}