Cod sursa(job #1655760)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 18 martie 2016 12:00:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#define pp pair<double,double>
#define w 120005
#define x first
#define y second
using namespace std;
inline double det(pp A,pp B,pp C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
pp v[w];
inline bool com(pp A,pp B)
{
    return (det(v[1],A,B)<0);
}
unsigned int st[w];
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int n,i,vf,k=1,l;double x,y;
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>x>>y;
        v[i]=make_pair(x,y);
        if (v[i]<v[k]) k=i;
    }
    swap(v[1],v[k]);
    sort(v+2,v+n+1,com);
    st[1]=1;st[2]=2;vf=2;
    for (i=3;i<=n;i++)
    {
        l=st[vf-1];k=st[vf];
        while (vf>=2 && det(v[l],v[k],v[i])>0)
        {
            vf--;
            l=st[vf-1];k=st[vf];
        }
        st[++vf]=i;
    }
    g<<vf<<'\n';
    g<<setprecision(6)<<fixed;
    for (i=vf;i>=1;i--)
    {
        g<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
    }
    f.close();
    g.close();
    return 0;
}