Cod sursa(job #1644492)

Utilizator zertixMaradin Octavian zertix Data 9 martie 2016 23:41:13
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

pair < double ,double > punc[120005];
int n;
int st[120005];
double det(pair <double ,double > x,pair <double ,double > y, pair <double,double > z)
{
    return ((y.first-x.first)*(z.second-x.second)-(y.second-x.second)*(z.first-x.first));
}
int cmp(pair <double,double > x,pair < double ,double >y)
{
    return det(punc[1],x,y)>0;
}
void citire()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        scanf("%lf%lf",&punc[i].first,&punc[i].second);
    int p=1;
    for (int i=2;i<=n;++i)
        if (punc[i]<punc[p])
            p=i;
    swap(punc[1],punc[p]);
    sort(punc+1,punc+n+1,cmp);
    st[1]=1;
    st[2]=2;
}
void infasuratoare()
{
    int k=2;
    for (int i=3;i<=n;++i)
    {
        while (k>=2 && det(punc[st[k]],punc[st[k-1]],punc[i])>0)
            --k;
        st[++k]=i;
    }
    printf("%d\n",k);
    for (int i=1;i<=k;++i)
        printf("%lf %lf\n",punc[st[i]].first,punc[st[i]].second);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    infasuratoare();
    return 0;
}