Cod sursa(job #1021419)

Utilizator misinozzz zzz misino Data 3 noiembrie 2013 20:01:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define punct pair<double,double>
#define x first
#define y second
#define N 120010
#define eps 0.000000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,l,vf,st[N],viz[N];
punct v[N];
inline double sarrus(punct c,punct a,punct b)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1);
    st[1]=1;
    st[2]=2;
    vf=2;
    viz[2]=1;
    for(i=1,l=1;i;i+=l)
    {
        if(i==n)
        l=-1;
        if(viz[i])
        continue;
        while(vf>=2&&sarrus(v[st[vf-1]],v[st[vf]],v[i])<eps)
        viz[st[vf--]]=0;
        st[++vf]=i;
        viz[i]=1;
    }
    g<<vf-1<<'\n'<<fixed<<setprecision(6);
    for(i=1;i<vf;++i)
    g<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
    return 0;
}