Cod sursa(job #363667)

Utilizator APOCALYPTODragos APOCALYPTO Data 14 noiembrie 2009 09:20:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <algorithm>
using namespace std;

#define DIM 120005

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

void sch (punct &a,punct &b)
{
    punct aux=a;

    a=b;
    b=aux;
}

void read ()
{
    int i;

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

int cmp (punct a,punct b)
{
    return (a.x-v[1].x)*(b.y-v[1].y)<(b.x-v[1].x)*(a.y-v[1].y);
}

int cotire (punct a,punct b,punct c)
{
    if (a.x*b.y+b.x*c.y+c.x*a.y>a.y*b.x+b.y*c.x+c.y*a.x)
        return 1;
    return 0;
}

void solve ()
{
    int i;

    for (st[++vf]=1, i=2; i<=n; st[++vf]=i++)
        for ( ; vf>=2 && cotire (v[st[vf-1]],v[st[vf]],v[i])>0; --vf);
}

void print ()
{
    int i;

    printf ("%d\n",vf);
    for (i=vf; i; --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 ();
    sort (v+2,v+n+1,cmp);
    solve ();
    print ();

    return 0;
}