Cod sursa(job #922067)

Utilizator cat_red20Vasile Ioana cat_red20 Data 21 martie 2013 21:54:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#include<algorithm>
#define MAXN 120000
#define err 0.000000000001
using namespace std;
struct punct
{
    double x,y;
}v[MAXN+1];
int st[MAXN+1],u,viz[MAXN+1],n;
void citire()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
    }
}

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


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

void infasura()
{
    st[1]=1;
    st[2]=2;
    viz[2]=1;
    viz[1]=1;
    u=2;
    for(int i=3;i<=n;i++)
    {
        while(u>=2 && produs(v[st[u-1]],v[st[u]],v[i])<err)
        {
            viz[st[u]]=0;
            u--;
        }
        st[++u]=i;
        viz[i]=1;
    }
    for(int i=n;i>0;i--)
    {
        if(viz[i])
        continue;
        while(u>=2 && produs(v[st[u-1]],v[st[u]],v[i])<err)
        {
            viz[st[u]]=0;
            u--;
        }
        st[++u]=i;
        viz[i]=1;
    }
    while(produs(v[st[u]],v[st[1]],v[st[2]])<err || produs(v[st[u-1]],v[st[u]],v[st[1]])<err)
    u--;
}

void afisare()
{
    freopen("infasuratoare.out","w",stdout);
    printf("%d",u);
    for(int i=1;i<=u;i++)
    printf("\n%.6lf %.6lf",v[st[i]].x, v[st[i]].y);
}

int main()
{
    citire();
    sort(v+1,v+n+1,cmp);
    infasura();
    afisare();
    return 0;
}