Cod sursa(job #1671472)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 1 aprilie 2016 19:34:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <algorithm>

using namespace std;
struct z
{
    double x,y;
}v[120001];
double X,Y;
int stiva[120001];
bool comp(z p1,z p2)
{
    return (p1.y-Y)*(p2.x-X)>(p2.y-Y)*(p1.x-X);
}
int main()
{
    int n,p,i,vf,min;
    double eps,aux;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    eps=0.000000000000;
    scanf("%d",&n);
    min=1000000000;
    p=0;
    for(i=1; i<=n; i++){
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if(min>v[i].x)
            min=v[i].x,p=i;
    }
    aux=v[1].x;
    v[1].x=v[p].x;
    v[p].x=aux;
    aux=v[1].y;
    v[1].y=v[p].y;
    v[p].y=aux;
    X=v[1].x;
    Y=v[1].y;
    sort(v+2,v+1+n,comp);
    stiva[1]=1;
    stiva[2]=2;
    stiva[3]=3;
    vf=3;
    for(i=4; i<=n; i++){
        while(vf>2 && (v[stiva[vf]].y-v[stiva[vf-1]].y)*(v[i].x-v[stiva[vf-1]].x)<(v[i].y-v[stiva[vf-1]].y)*(v[stiva[vf]].x-v[stiva[vf-1]].x))
            vf--;
        stiva[++vf]=i;
    }
    printf("%d\n",vf);
    for(i=vf; i>0; i--)
        printf("%lf %lf\n",v[stiva[i]].x,v[stiva[i]].y);

    return 0;
}