Cod sursa(job #1525951)

Utilizator seby5381Marinescu Sebastian seby5381 Data 15 noiembrie 2015 18:57:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int st[120007],ap[120007],n,i,nr;

struct punct
{
    double x,y;
}pct[120007];

double EPS=0.0000000000001;

int modul(double x)
{
    if(x<=0) return -x;
    return x;
}

bool egal(double x, double y)
{
    return (modul(x-y)<=EPS);
}

bool cmp(punct m, punct n)
{
    if(egal(m.x,n.x)) return m.y<n.y;
    return m.y<n.y;
}

//A.x A.y 1;
//B.x B.y 1;
//C.x C.y 1;
//A.x A.y 1;
//B.x B.y 1;

double det(punct A, punct B, punct C)
{
    return (double)A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-A.x*C.y-B.x*A.y;
}

void elimin(int i)
{
    while(nr>=2&&det(pct[st[nr-1]],pct[st[nr]],pct[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",&pct[i].x,&pct[i].y);

    sort(pct+1,pct+n+1,cmp);

    nr=2;
    st[1]=1;
    st[2]=2;
    ap[2]=1;
    for(i=3;i<=n;i++)
    {
        if(ap[i]==0)
        {
            elimin(i);
            nr++;
            st[nr]=i;
            ap[i]=1;
        }
    }
    for(i=n;i>1;i--)
    {
        if(ap[i]==0)
        {
            elimin(i);
            nr++;
            st[nr]=i;
            ap[i]=1;
        }
    }
    elimin(1);
    printf("%d\n",nr);
    for(i=1;i<=nr;i++)
        printf("%.6lf %.6lf\n",pct[st[i]].x,pct[st[i]].y);
    return 0;
}