Cod sursa(job #2288625)

Utilizator CojocaruVicentiuCojocaru Vicentiu CojocaruVicentiu Data 23 noiembrie 2018 18:22:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
#define pp pair < double, double >

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

pp p[120010];
int i,n,st[120010];

double determ(pp a, pp b, pp c)
{
    double ans= a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - c.y*a.x - a.y*b.x;
    return ans;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>p[i].x>>p[i].y;
    }
    sort(p+1,p+n+1);
    st[1]=1;
    st[2]=2;
    st[0]=2;
    for(i=3;i<=n;i++)
    {
        while(st[0]>1 && determ(p[st[st[0]-1]],p[st[st[0]]],p[i])>0)
            st[0]--;
        st[++st[0]]=i;
    }
    for(i=n-1;i>=1;i--)
    {
        while(determ(p[st[st[0]-1]],p[st[st[0]]],p[i])>0)
            st[0]--;
        st[++st[0]]=i;
    }
    fout<<st[0]-1<<'\n';
    for(i=st[0]-1;i>=1;i--)
        fout<<setprecision(6)<<fixed<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';





    fin.close();
    fout.close();
    return 0;
}