Cod sursa(job #1587515)

Utilizator cristina_borzaCristina Borza cristina_borza Data 2 februarie 2016 10:34:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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 ;} v[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 , v[1]) < 0;
}

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

    sort(v + 1 , v + n + 1 , comp1);
    sort(v + 2 , v + n + 1 , comp2);

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

    for(int i = 3 ; i <= n ; ++i) {
        stiva[++vf] = v[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(10) << fixed << stiva[i] . x << " " << stiva[i] . y << '\n';
    }

    return 0;
}