Cod sursa(job #1623585)

Utilizator gerd13David Gergely gerd13 Data 1 martie 2016 20:28:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define x first
#define y second

using namespace std ;

const int NMAX = 120005 ;
const double e = 1e-12 ;


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

pair <double, double> V[NMAX] ;
bool use[NMAX] ;
int st[NMAX], head, N ;

double cross_product(pair <double, double> O, pair <double, double> A, pair <double, double> B)
{
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y) ;
}

int main()
{
    fin >> N ;

    for(int i  = 1 ; i <= N ; ++ i )
        fin >> V[i].first >> V[i].second ;

    sort(V + 1, V + N + 1) ;

    int p = 1 ;

    st[1] = 1 ;
    st[2] = head = 2 ;
    use[2] = 1;

    for(int i = 1 ; i > 0  ; i = i + p)
    {


        if(i == N)
            p = -1 ;

        if(use[i])
            continue ;


        while(head >= 2 && cross_product(V[st[head - 1]], V[st[head]], V[i]) < e)
            use[st[head --]] = 0 ;


        st[++head] = i ;
        use[i] = 1 ;
    }

    fout << head - 1 <<'\n';
    fout << fixed << setprecision(9) ;

    for(int i = 2  ; i <= head; ++ i)
        fout << V[st[i]].x << ' ' << V[st[i]].y << '\n' ;


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