Cod sursa(job #891642)

Utilizator gabriel93Robu Gabriel gabriel93 Data 25 februarie 2013 18:31:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 120002
using namespace std;
int n,ns;

struct punct
{
    double x,y;
};
punct v[Nmax],st[Nmax];

double cross_prod(punct p1,punct p2,punct p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x);
}

int cmp(punct p1,punct p2)
{
    if (cross_prod(v[1],p1,p2)<0)
        return 1;
    return 0;
}

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

void sortare()
{
    int start,i;
    start=1;
    for(i=2;i<=n;++i)
        if(v[i].x < v[start].x)
            start=i;
        else
            if(v[i].x==v[start].x && v[i].y < v[start].y)
                start=i;
    swap(v[start],v[1]);
    sort(v+2,v+n+1,cmp);
}

void rezolv()
{
    int i;
    sortare();
    st[1]=v[1];
    st[2]=v[2];
    ns=2;
    for(i=3;i<=n;++i)
    {
        while(ns>=2 && cross_prod(st[ns-1],st[ns],v[i])>0)
            ns--;
        ++ns;
        st[ns]=v[i];
    }
}

void scrie()
{
    int i;
    printf("%d\n",ns);
    for(i=ns;i>=1;--i)
        printf("%lf %lf\n",st[i].x,st[i].y);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    rezolv();
    scrie();
    fclose(stdin);
    fclose(stdout);
    return 0;
}