Cod sursa(job #1373818)

Utilizator gerd13David Gergely gerd13 Data 4 martie 2015 20:44:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>


#define x first
#define y second

using namespace std ;

typedef pair <double, double> Pair ;

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



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

int N ;

Pair V[NMAX] ;
bool use[NMAX]  ;
int vf, st[NMAX] ;

double cross_product(Pair O, Pair A, Pair 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) ;

    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])
            continue ;
        while(vf >= 2 && (cross_product(V[st[vf - 1]], V[st[vf]], V[i])) < EPS )
            use[st[vf -- ]] = false ;
        st[++ vf] = i ;
        use[i] = true ;
    }

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

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

    fout << '\n' ;




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