Cod sursa(job #2006874)

Utilizator robx12lnLinca Robert robx12ln Data 1 august 2017 10:02:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
#define DIM 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, poz, k;
pair< double, double > v[DIM], st[DIM];

inline double det( pair< double, double > A, pair< double, double > B, pair< double, double > C ){
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

inline int cmp( const pair< double, double > &A, const pair< double, double > &B ){
    return det( v[1], A, B ) < 0;
}

int main(){

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

    //determin punctul cel mai din stanga dar sicel mai de jos ( determin primul pct din infasuratoare )
    poz = 1;
    for( int i = 2; i <= n; i++ ){
        if( v[poz] > v[i] ){
            poz = i;
        }
    }

    //sortez dupa panta
    swap( v[1], v[poz] );
    sort( v + 2, v + n + 1, cmp );

    //bag algoritmul de determinare a infasuratoarii convexe ( scanarea Graham )
    k = 2;
    st[1] = v[1];
    st[2] = v[2];
    for( int i = 3; i <= n; i++ ){
        while( k >= 2 && det( st[k - 1], st[k], v[i] ) > 0 )
            k--;
        st[++k] = v[i];
    }
    fout << k << "\n";
    for( int i = 1; i <= k; i++ ){
        fout << setprecision(9) << fixed << st[i].x << " ";
        fout << setprecision(9) << fixed << st[i].y << "\n";
    }
    return 0;
}