Cod sursa(job #2053950)

Utilizator robx12lnLinca Robert robx12ln Data 1 noiembrie 2017 15:56:18
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define EPS 1e-12
#define DIM 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int f[DIM], n, st[DIM], k;
struct Point{
    double x, y;
} v[DIM];
inline double det( Point A, Point B, Point C ){
    return ( A.x - C.x ) * ( B.y - C.y ) - ( B.x - C.x ) * ( A.y - C.y );
}
inline int cmp( const Point &a, const Point &b ){
    if( ( a.x - b.x ) <= EPS && ( a.x - b.x ) >= -EPS )
        return ( a.y - b.y ) < EPS;
    return ( a.x - b.x ) < EPS;
}
int main(){
    fin >> n;
    for( int i = 1; i <= n; i++ )
        fin >> v[i].x >> v[i].y;
    sort( v + 1, v + n + 1, cmp );
    f[1] = f[2] = 1;
    st[1] = 1;
    st[2] = 2;
    k = 2;
    //lower_bound
    for( int i = 1; i <= n; i++ ){
        if( f[i] == 1 )
            continue;
        while( k > 1 && det( v[ st[k - 1] ], v[ st[k] ], v[i] ) < EPS ){
            f[ st[k] ] = 0;
            k--;
        }
        st[++k] = i;
        f[i] = 1;
    }
    //upper_bound
    for( int i = n; i >= 1; i-- ){
        if( f[i] == 1 )
            continue;
        while( k > 1 && det( v[ st[k - 1] ], v[ st[k] ], v[i] ) < EPS ){
            f[ st[k] ] = 0;
            k--;
        }
        st[++k] = i;
        f[i] = 1;
    }
    fout << k << "\n";
    for( int i = 1; i <= k; i++ ){
        fout << setprecision(9) << fixed << v[ st[i] ].x << " ";
        fout << setprecision(9) << fixed << v[ st[i] ].y << "\n";
    }
    return 0;
}