Cod sursa(job #1662143)

Utilizator felixiPuscasu Felix felixi Data 24 martie 2016 15:24:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>

using namespace std;

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

const int NMAX = 120000;
const double EPS = 1e-6;

struct PCT {
    double x,y;
};

vector <PCT> v, hull;
int N;

double cross_product(PCT A, PCT O, PCT B) {
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

bool cmp_PCT( PCT A, PCT B ) {
    return ( A.x < B.x || (A.x == B.x && A.y < B.y) );
}

void make_hull( vector<PCT> pct, vector<PCT> &hull ) {
    sort( pct.begin(), pct.end(), cmp_PCT );
    hull.clear();
    stack <int> st;
    st.push( 0 );  st.push( 1 );
    for( int i = 2;  i < (int)pct.size();  ++i ) {
        int ind2 = st.top();
        st.pop();
        int ind1 = st.top();
        st.push(ind2);
        while( (int)st.size()>1 && cross_product( pct[ind1], pct[ind2], pct[i] ) < EPS ) {
            st.pop();  ///  scot ind2

            ind2 = st.top();
            st.pop();
            if( !st.empty() )  ind1 = st.top();
            st.push(ind2);
        }
        st.push( i );
    }
    vector <PCT> sec;
    while( !st.empty() ) {
        hull.push_back( pct[ st.top() ] );
        st.pop();
    }
    reverse( hull.begin(), hull.end() );

    st.push( (int)pct.size() - 1 );
    st.push( (int)pct.size() - 2 );
    for( int i = (int)pct.size() - 3;  i >= 0;  --i ) {
        int ind2 = st.top();
        st.pop();
        int ind1 = st.top();
        st.push(ind2);
        while( (int)st.size()>1 && cross_product( pct[ind1], pct[ind2], pct[i] ) < EPS ) {
            st.pop();  ///  scot ind2

            ind2 = st.top();
            st.pop();
            if( !st.empty() )  ind1 = st.top();
            st.push(ind2);
        }
        st.push( i );
    }
    while( !st.empty() ) {
        sec.push_back( pct[ st.top() ] );
        st.pop();
    }
    reverse( sec.begin(), sec.end() );
    for( int i = 1;  i < (int)sec.size() - 1;  ++i )  hull.push_back( sec[i] );
    reverse( hull.begin(), hull.end() );
}

int main() {
    in >> N;
    for( int i = 1;  i <= N;  ++i ) {
        PCT p;
        in >> p.x >> p.y;
        v.push_back( p );
    }
    make_hull( v, hull );
    out << hull.size() << '\n';
    out << setprecision( 6 ) << fixed;
    for( int i = 0;  i < (int)hull.size();  ++i ) {
        out << hull[i].x << ' ' << hull[i].y << '\n';
    }
    return 0;
}