Cod sursa(job #1790239)

Utilizator mantisVraciu Stefan mantis Data 27 octombrie 2016 22:01:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,vf,poz,st[120005];
typedef pair<double,double> Punct;
Punct a[120005];
double determinant(Punct A, Punct B, Punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int comp(Punct A, Punct B)
{
    return (determinant(a[1],A,B)<0);
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>a[i].x>>a[i].y;
        if(a[i]<a[poz]) poz=i;
    }
    swap(a[1],a[poz]);
    sort(a+2,a+n+1,comp);
    st[++vf]=1;
    for(int i=2;i<=n;i++)
    {
        while(vf>1 && determinant(a[st[vf-1]],a[st[vf]],a[i])>0) vf--;
        st[++vf]=i;
    }
    g<<vf<<'\n';
    while(vf)
    {
        g<<fixed<<setprecision(6)<<a[st[vf]].x<<' '<<a[st[vf]].y<<'\n';
        vf--;
    }
    g.close();
    return 0;
}