Cod sursa(job #1409688)

Utilizator misinoonisim necula misino Data 30 martie 2015 17:41:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<fstream>
#include<algorithm>
#include<iomanip>

#define N 120100
#define eps 1e-12

using namespace std;

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

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

struct punct{double x,y;}v[N];

inline double sarrus(punct a, punct b, punct c){
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline bool cmp(punct a, punct b){
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    f >> n;

    for(i = 1; i <= n; ++i)
        f >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1, cmp);

    st[1] = 1;
    st[2] = 2;
    viz[2] = 1;
    vf = 2;

    for(i = 3, p = 1; i; i += p)
        if(!viz[i])
        {
            if(i == n)
                 p = -1;

            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';

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

    return 0;
}