Cod sursa(job #411078)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 4 martie 2010 18:34:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<algorithm>
#define Nmx 120001

using namespace std;

struct coord
{
    double x,y;
};
coord a[Nmx],st[Nmx];

int n,pz,nr;

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

struct cmp
{
    bool operator()(const coord &A,const coord &B) const
    {
        return (double)(a[1].y-A.y)*(a[1].x-B.x)<(double)(a[1].y-B.y)*(a[1].x-A.x);
    }
};

double semn(double xa,double ya,double xb,double yb,double xc,double yc)
{
    return xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    coord aux;
    aux=a[pz];
    a[pz]=a[1];
    a[1]=aux;
    sort(a+2,a+n+1,cmp());
    st[++nr]=a[1];
    for(int i=2;i<=n;++i)
    {
        while(nr>=2&&semn(st[nr-1].x,st[nr-1].y,st[nr].x,st[nr].y,a[i].x,a[i].y)<0)
            --nr;
        st[++nr]=a[i];
    }
    printf("%d\n",nr);
    for(int i=1;i<=nr;++i)
        printf("%.6lf %.6lf\n",st[i].x,st[i].y);
    return 0;
}