Cod sursa(job #559791)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 18 martie 2011 08:41:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<cstdio>
#include<algorithm>
#define Nmx 120001
#define INF 10000001.0

using namespace std;

int n,pct=1,nr;
struct dat
{
    double x,y,panta;
};
dat a[Nmx],st[Nmx];

struct cmp
{
    bool operator ()(const dat &A,const dat &B)
    {
        if(A.panta==B.panta)
            if(A.x==B.x)
                return A.y<B.y;
            else return A.x<B.x;
        else return A.panta<B.panta;
    }
};

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

double pnt(double x1,double y1,double x2,double y2)
{
    if(x2-x1==0)
        return INF;
    return (y2-y1)/(x2-x1);
}

void calc()
{
    for(int i=1;i<=n;++i)
    {
        a[i].panta=-INF;
        if(pct!=i)
            a[i].panta=pnt(a[pct].x,a[pct].y,a[i].x,a[i].y);
    }
    sort(a+1,a+n+1,cmp());
}

double semn(double x1,double y1,double x2,double y2,double x3,double y3)
{
    return x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
}

void infasuratoare()
{
    nr=1;
    st[1]=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);
}

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