Cod sursa(job #1623650)

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

#define x first
#define y second

using namespace std ;

typedef pair <double, double> Pair ;



const int NMAX = 120005 ;

Pair V[NMAX], S[NMAX], MIN(1000000000, 1000000000) ;
int head, N ;


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

inline double cross_product(Pair O, Pair A, Pair B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x) ;
}

inline double cmp(Pair A, Pair B)
{
    return (A.x - MIN.x) * (B.y - MIN.y) > (B.x - MIN.x) * (A.y - MIN.y) ;
}

int main()
{

    int pos ;
    fin >> N ;

    for(int i = 1 ; i <= N ; ++ i)
    {
        Pair XY ;
        fin >> XY.x >> XY.y ;

        if(XY < MIN)
            MIN = XY, pos = i  ;
        V[i] = XY ;
    }

    swap(V[1], V[pos]) ;
    sort(V + 2, V + N  + 2, cmp) ;

    S[1] = V[1] ;
    S[2] = V[2] ;

    for(int i = 3 ; i <= N ; ++ i)
    {
        while(head >= 2 && cross_product(V[head - 1], V[head], V[i]) < 0)
            -- head  ;

            S[++head] = V[i] ;
    }

    fout << head << '\n' ;

    fout << fixed << setprecision(9) ;

    for(int i = 1 ; i <= head; fout << S[i].x << ' ' << S[i].y << '\n', i ++)

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

}