Cod sursa(job #1067655)

Utilizator acomAndrei Comaneci acom Data 27 decembrie 2013 11:28:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct
{
    double x,y;
} a[120005];
int n,k,poz=1;
int st[120005];

double det(punct a, punct b, punct c) {
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}

int cmp(punct a, punct b) {
    punct c;
    c.x = c.y = 0;
    return det(c,a,b) >=0 ;

}

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