Cod sursa(job #1379472)

Utilizator misinozzz zzz misino Data 6 martie 2015 18:01:42
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<algorithm>
#include<iomanip>

#define eps 1e-12
#define N 120100
#define x first
#define y second

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int i,n,vf,pas,st[N],viz[N];

pair<double,double>v[N];

inline double Sarrus(pair<int,int> a, pair<int,int> b,pair<int,int> c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

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;
    pas = 1;
    for(i = 1; i; i += pas)
        if(!viz[i])
        {
            while(vf >= 2 && Sarrus(v[st[vf - 1]], v[st[vf]], v[i]) < eps)
                viz[st[vf]] = 0,
                --vf;
            st[++vf] = i;
            viz[i] = 1;

            if(i == n)
                pas = -1;
        }

    g << vf - 1 << '\n';

    for(i = 1; i < vf; ++i)
        g << fixed << setprecision(6) << v[st[i]].x << ' ' << v[st[i]].y << '\n';

    return 0;
}