Cod sursa(job #2019037)

Utilizator victoreVictor Popa victore Data 6 septembrie 2017 18:25:20
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int nmax=120005;
const double eps=1e-12;


int n,m,top;

struct point
{
    double x,y;
}punct[nmax],st[nmax];

inline int cp(point p1,point p2,point p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y) - (p2.y-p1.y)*(p3.x-p2.x);
}

inline bool cmp(const point &p1, const point &p2)
{
    if(fabs(p1.x - p2.x) > eps)
        return p2.x - p1.x > eps;
    return p2.y - p1.y > eps;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%lf%lf",&punct[i].x,&punct[i].y);
    sort(punct+1,punct+n+1,cmp);
    st[++top]=punct[1];
    st[++top]=punct[2];
    for(i=3;i<=n;++i)
    {
        while(top > 1 && cp(st[top-1],st[top],punct[i]) <=-eps)
                --top;
        st[++top]=punct[i];
    }
    for(i=n-1;i;--i)
    {
        while(top>1 && cp(st[top-1] , st[top] ,punct[i]) <=-eps)
            --top;
        st[++top]=punct[i];
    }
    printf("%d\n",top-1);
    for(i=1;i<top;++i)
        printf("%lf %lf\n",st[i].x,st[i].y);
    return 0;
}