Cod sursa(job #2019041)

Utilizator victoreVictor Popa victore Data 6 septembrie 2017 18:36:05
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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];
int 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]=1;
    st[++top]=2;
    for(i=3;i<=n;++i)
    {
        while(top > 1 && cp(punct[st[top-1]],punct[st[top]],punct[i]) <=-eps)
                --top;
        st[++top]=i;
    }
    for(i=n-1;i;--i)
    {
        while(top > 1 && cp(punct[st[top-1]],punct[st[top]],punct[i]) <=-eps)
            --top;
        st[++top]=i;
    }
    printf("%d\n",top-1);
    for(i=1;i<top;++i)
        printf("%lf %lf\n",punct[st[i]].x,punct[st[i]].y);
    return 0;
}