Cod sursa(job #2156318)

Utilizator andrei20003Ionescu Andrei andrei20003 Data 8 martie 2018 17:23:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

struct pt
{
    double x,y;
};
pt v[120001],st[120001],v2[120001];

bool cmp(pt a,pt b){
    if (a.x<b.x)
        return true;
    if (a.x==b.x)
        if (a.y<b.y)
            return true;
    return false;
}

bool semnarie (pt p1,pt p2,pt p3) {
    return (p2.x*p1.y+p3.x*p2.y+p1.x*p3.y-p1.x*p2.y-p2.x*p3.y-p3.x*p1.y)<0;
}

int main()
{
    int n,i,b=0,a;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w'",stdout);
    scanf("%d", &n);
    for (i=0;i<n;i++)
        scanf("%lf%lf", &v[i].x, &v[i].y);
    sort(v,v+n,cmp);
    st[++b]=v[0];
    for (i=1;i<n;i++) {
        while (b>1 && !semnarie(st[b-1],st[b],v[i]))
            b--;
        st[++b]=v[i];
    }
    a=b;
    for (i=1;i<=b;i++)
        v2[i]=st[i];
    b=0;
    st[++b]=v[n-1];
    for (i=n-2;i>=0;i--) {
        while (b>1 && !semnarie(st[b-1],st[b],v[i]))
            b--;
        st[++b]=v[i];
    }
    for (i=2;i<=b;i++)
        v2[i+a-1]=st[i];
    a=a+b-2;
    printf("%d\n",a);
    for(i=1;i<=a;i++)
        printf("%lf %lf\n",v2[i].x,v2[i].y);
    return 0;
}