Cod sursa(job #1545884)

Utilizator Athena99Anghel Anca Athena99 Data 7 decembrie 2015 12:21:33
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>

using namespace std;

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

const int nmax= 120000;
const int out_precision= 6;

struct str {
    double x, y;
};

str v[nmax+1];

vector <int> sol;

double arie( str x, str y, str z ) {
    double ans= (double)((y.x-x.x)*(z.y-x.y)-(z.x-x.x)*(y.y-x.y))/2;
    return ans;
}

bool cmp( str x, str y ) {
    return arie(v[1], x, y)<0;
}

int main(  ) {
    int n, pos= 1;
    fin>>n;
    for ( int i= 1; i<=n; ++i ) {
        fin>>v[i].x>>v[i].y;
        if ( v[i].y<v[pos].y ) {
            pos= i;
        }
    }
    str aux= v[1];
    v[1]= v[pos], v[pos]= aux;
    sort( v+2, v+n+1, cmp );

    sol.push_back(1);
    for ( int i= 2; i<=n; ++i ) {
        for ( ; (int)sol.size()>=2 && arie(v[sol[(int)sol.size()-2]], v[sol.back()], v[i])>0; sol.pop_back() ) ;
        sol.push_back(i);
    }

    fout<<(int)sol.size()<<"\n";
    fout<<setprecision(out_precision)<<fixed;
    for ( int i= 0; i<(int)sol.size(); ++i ) {
        fout<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
    }

    return 0;
}