Cod sursa(job #1466897)

Utilizator cristina_borzaCristina Borza cristina_borza Data 31 iulie 2015 16:24:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

#define NMAX 150000

using namespace std;

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

int n , vf ;
struct elem{double x , y ;} a[NMAX] , stiva[NMAX];


double arie(elem q, elem b , elem c) {
    double rez = 0;
    rez += q . x * b . y;
    rez += q . y * c . x;
    rez += b . x * c . y;

    rez -= q . x * c . y;
    rez -= q . y * b . x;
    rez -= b . y * c . x;

    return rez / 2;
}

bool comp1(elem a , elem b){
    return a . x < b . x || (a . x == b . x && a . y < b . y) ;
}

bool comp2(elem q , elem b){
    return arie(q , b , a[1]) < 0 ;
}

int main()
{
    f >> n ;
    for(int i = 1 ; i <= n ; ++i){
        f >> a[i].x >> a[i].y ;
    }

    sort(a + 1 , a + n + 1 , comp1) ;

    sort(a + 2 , a + n + 1 , comp2) ;

    stiva[1] = a[1] ;
    stiva[2] = a[2] ;
    vf = 2 ;

    for(int i = 3 ; i <= n ; ++i){
        stiva[++vf] = a[i] ;
        while(vf > 3 && arie(stiva[vf] , stiva[vf - 1] , stiva[vf - 2]) < 0){
            stiva[vf - 1] = stiva[vf] ;
            --vf ;
        }
    }

    g << vf << '\n' ;
    for(int i = vf ; i >= 1 ; --i){
        g << setprecision(13) << fixed << stiva[i] . x << " " << stiva[i] . y << '\n' ;
    }

    return 0;
}