Cod sursa(job #411076)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 4 martie 2010 18:33:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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[i].x<a[pz].x)
               pz=i;
             else if(a[i].x==a[pz].x)
                    if(a[i].y<a[pz].y)
                      pz=i;
    }
}

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

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=nr;i>=1;--i)
        printf("%.6lf %.6lf\n",st[i].x,st[i].y);
    return 0;
}