Cod sursa(job #582694)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 15 aprilie 2011 18:36:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <cstring>
#include <fstream>
#define INF 10000001.0
#define Nmx 120005

using namespace std;

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

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

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

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



void prepro()
{
    for(int i=1;i<=n;++i)
    {
        a[i].panta=-INF;
        if(i!=pct)
            a[i].panta=calc(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 solve()
{
    st[++nr]=a[1];
    st[++nr]=a[2];
    for(int i=3;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);
    read();
    prepro();
    solve();
    return 0;
}