Cod sursa(job #1622639)

Utilizator gerd13David Gergely gerd13 Data 1 martie 2016 12:59:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>


using namespace std ;

const int INF = 0x3f3f3f3f ;
const int NMAX = 120005 ;
const double EPS = 1e-12 ;

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

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


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

int main()
{
    fin >> N ;

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


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

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


    use[2] = 1 ;

    for(int i = 1, p = 1 ; i > 0 ; i = i + (p = (i == N ? -p : p)))
        if(!use[i])
        {
            while(vf >= 2 && (cross_product(V[st[vf - 1]], V[st[vf]], V[i]) < EPS))
                use[st[vf --]] = 0 ;
            st[ ++ vf] = i  ;
            use[i] = 1 ;
        }

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

    fout << fixed << setprecision(9) ;

    for(int i = 1 ; i < vf ; ++ i)
        fout << V[st[i]].first << ' ' << V[st[i]].second << '\n' ;



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