Cod sursa(job #2376499)

Utilizator robx12lnLinca Robert robx12ln Data 8 martie 2019 16:00:32
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include<bits/stdc++.h>
using namespace std;

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

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

int N, st[DIM], f[DIM], K;
struct point{
    double x, y;
} P[DIM];

double det( point S1, point S2, point P0 ){
    return ( S1.x - P0.x ) * ( S2.y - P0.y ) - ( S2.x - P0.x ) * ( S1.y - P0.y );
}

inline bool 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 >> P[i].x >> P[i].y;

    sort( P + 1, P + N + 1, cmp );
    f[2] = 1;
    st[1] = 1; st[2] = 2;
    K = 2;

    ///lower-bound
    for( int i = 3; i <= N; i++ ){
        while( K > 1 && det( P[ st[K - 1] ], P[ st[K] ], P[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( P[ st[K - 1] ], P[ st[K] ], P[i] ) < EPS )
            f[ st[K] ] = 0, K--;
        st[++K] = i;
        f[i] = 1;
    }
    K--; ///pct cel mai din stanga apare de 2 ori
    fout << K << "\n";
    for( int i = 1; i <= K; i++ ){
        fout << setprecision(9) << fixed << P[ st[i] ].x << " ";
        fout << setprecision(9) << fixed << P[ st[i] ].y << "\n";
    }
    return 0;
}