Cod sursa(job #406381)

Utilizator DraStiKDragos Oprica DraStiK Data 1 martie 2010 14:55:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
#define DIM 120005

struct punct {double x,y;} v[DIM];
int ind[DIM],st[DIM];
int n,vf,o;

void read ()
{
    int i;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
    {
        scanf ("%lf%lf",&v[i].x,&v[i].y);
        if (i==1 || v[i].x<v[o].x || (v[i].x==v[o].x && v[i].y<v[o].y))
            o=i;
        ind[i]=i;
    }
}

inline double panta (const int &a,const int &b)
{
    if (v[a].x==v[b].x)
        return INF;
    return (v[a].y-v[b].y)/(v[a].x-v[b].x);
}

struct cmp
{
    bool operator () (const int &a,const int &b) const
    {
        return panta (o,a)>panta (o,b);
    }
};

inline double semn (const int &a,const int &b,const int &c)
{
    return (v[b].x-v[a].x)*(v[c].y-v[a].y)-(v[c].x-v[a].x)*(v[b].y-v[a].y);
}

void solve ()
{
    int i;

    sort (ind+1,ind+n+1,cmp ());
    st[vf=1]=o;
    for (i=1; i<=n; ++i)
        if (ind[i]!=o)
        {
            for ( ; vf>=2 && semn (st[vf-1],st[vf],ind[i])>0; --vf);
            st[++vf]=ind[i];
        }
}

void print ()
{
    int i;

    printf ("%d\n",vf);
    for (i=vf; i>=1; --i)
        printf ("%lf %lf\n",v[st[i]].x,v[st[i]].y);
}

int main ()
{
    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);

    read ();
    solve ();
    print ();

    return 0;
}