Cod sursa(job #526856)

Utilizator DraStiKDragos Oprica DraStiK Data 29 ianuarie 2011 17:52:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
#define DIM 120005
#define sc second
#define fs first

pair <double,double> v[DIM];
int ind[DIM],st[DIM];
int n,o,vf;

void read ()
{
    int i;

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

inline double panta (int a,int b)
{
    if (v[a].fs==v[b].fs)
        return INF;
    else
        return (v[a].sc-v[b].sc)/(v[a].fs-v[b].fs);
}

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

inline double det (int a,int b,int c)
{
    return (v[b].fs-v[a].fs)*(v[c].sc-v[a].sc)-(v[c].fs-v[a].fs)*(v[b].sc-v[a].sc);
}

void solve ()
{
    int i;

    sort (ind+1,ind+n+1,cmp ());
    st[++vf]=o;
    for (i=1; i<=n; ++i)
        if (ind[i]!=o)
        {
            for ( ; vf>=2 && det (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 ("%.6lf %.6lf\n",v[st[i]].fs,v[st[i]].sc);
}

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

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

    return 0;
}