Cod sursa(job #1524166)

Utilizator binicBinica Nicolae binic Data 13 noiembrie 2015 16:45:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<cstdio>
#include<algorithm>
#define eps 0.000000000001
using namespace std;
int n,i,nr,ap[120004],st[120004];
struct pct
{
    double x,y;
}a[120004];

double mod(double x)
{
    if(x<0)return -x;
    return x;
}

bool egal(double x,double y)
{
    return (mod(x-y)<=eps);
}

bool cmp(pct x,pct y)
{
    if(egal(x.x,y.x))return x.y<y.y;
    return x.x<y.x;
}
//A.x A.y 1;
//B.x B.y 1;
//C.x C.y 1;
double det(pct A,pct B,pct C)
{
    return (double) A.x*B.y + B.x*C.y + C.x*A.y - C.x*B.y - B.x*A.y - A.x*C.y;
}
void elim(int i)
{
    while(nr>=2&& det ( a[st[nr-1]] , a[st[nr]] , a[i] ) <eps)
    {
        ap[st[nr]]=0;
        nr--;
    }
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf %lf",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    st[1]=1;
    st[2]=2;
    ap[2]=1;
    nr=2;
    for(i=3;i<=n;i++)
    {
        elim(i);
        nr++;
        st[nr]=i;
        ap[i]=1;
    }
    for(i=n;i>1;i--)
        if(ap[i]==0)
        {
            elim(i);
            nr++;
            st[nr]=i;
            ap[i]=1;
        }
    elim(1);
    printf("%d\n",nr);
    for(i=1;i<=nr;i++)
        printf("%.6lf %.6lf\n",a[st[i]].x,a[st[i]].y);
    return 0;
}