Cod sursa(job #1247789)

Utilizator felixiPuscasu Felix felixi Data 23 octombrie 2014 20:44:49
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <cstring>
#include <iomanip>
#include <cmath>

using namespace std;

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

const int NMAX   = 120000;
const double EPS = 1.e-12;

struct PCT{
    double x,y;
};
///  Const pt infasuratoare
PCT XX;
///  Restul
vector <PCT> v, r;
int N;

bool Alege_XX( PCT A ) {
    return (  A.x < XX.x || ( fabs(A.x-XX.x)<EPS && A.y < XX.y )  );
}

double CCW( PCT A, PCT B, PCT C ) {
    double val= (B.x-A.x)*(C.y-B.y) - (B.y-A.y)*(C.x-B.x);
    if( val >= EPS ) return 1;
    if( val <= -EPS ) return -1;
    return 0;
}

bool cmp_panta( PCT A, PCT B ) {
    return ( CCW( XX, A, B ) > 0.0 );
}

void Infas_Convexa( vector<PCT> &v, vector<PCT> &r ) {
    r.clear();

    PCT st[NMAX+2];  int st_ind= 0;
    sort( v.begin(), v.end(), cmp_panta );

    st[ ++st_ind ]= v[0];   r.push_back( v[0] );
    st[ ++st_ind ]= v[1];   r.push_back( v[1] );

    for( int i= 2;  i<(int)v.size();  ++i ) {
        if( CCW( st[ st_ind-1 ], st[ st_ind ], v[i] ) > 0.0 ) {
            st[ ++st_ind ]= v[i];   /// Pun in stiva
            r.push_back( v[i] );
        }
        else {
            --st_ind;                /// Scot
            st[ ++st_ind ]= v[i];   /// Pun elementul curent
            r[ st_ind - 1 ]= v[i];
        }
    }
}

int main() {
    in >> N;
    in >> XX.x >> XX.y;
    for( int i= 2;  i<=N;  ++i ) {
        PCT a;  double r1,r2;
        in >> r1 >> r2;   a.x= r1;  a.y= r2;
        v.push_back( a );
        if ( Alege_XX( a ) ) {
            swap( a, v[0] );
            XX= v[0];
        }
    }
    PCT aux= v[0];
    v.push_back( v[0] );     ///  Adaug la coada primul element
    Infas_Convexa( v, r );

    out << (int)r.size() << '\n';
    for( int i= 0;  i<(int)r.size();  ++i ) {
        out << fixed << setprecision(12) << r[i].x << ' ' << r[i].y << '\n';
    }

    return 0;
}