Cod sursa(job #2565063)

Utilizator robx12lnLinca Robert robx12ln Data 2 martie 2020 11:55:40
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include<bits/stdc++.h>
#define punct pair<double,double>
#define x first
#define y second
using namespace std;

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

const int DIM = 120005;
const double EPS = 1e-12;

int N;
bool f[DIM];
vector<int> st;

punct arr[DIM];

double cross_product( punct S1, punct S2, punct P ){
    return ( S2.x - P.x ) * ( S1.y - P.y ) - ( S1.x - P.x ) * ( S2.y - P.y );
}

int main(){

    fin >> N;
    for( int i = 1; i <= N; i++ )
        fin >> arr[i].x >> arr[i].y;

    sort( arr + 1, arr + N + 1 );
    st.push_back(1);
    st.push_back(2);
    f[2] = true;
    ///lower_bound
    for( int i = 3; i <= N; i++ ){
        while( st.size() > 2 && cross_product( arr[ st[ st.size() - 2 ] ], arr[ st[ st.size() - 1 ] ], arr[i] ) < EPS )
            f[ st.back() ] = false, st.pop_back();
        f[i] = true;
        st.push_back( i );
    }

    ///upper_bound
    for( int i = N; i >= 1; i-- ){
        if( f[i] == true )
            continue;
        while( st.size() > 2 && cross_product( arr[ st[ st.size() - 2 ] ], arr[ st[ st.size() - 1 ] ], arr[i] ) < EPS )
            f[ st.back() ] = false, st.pop_back();
        f[i] = true;
        st.push_back( i );
    }

    st.pop_back();
    fout << (int)(st.size()) << "\n";
    for( int i = st.size() - 1; i >= 0; i-- ){
        fout << setprecision(10) << fixed << arr[ st[i] ].x << " " << arr[ st[i] ].y << "\n";
    }
    return 0;
}