Cod sursa(job #2572583)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 5 martie 2020 13:27:11
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 120005;

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

int N;
struct punct
{
    double x, y;
};

punct P[NMAX];
punct A, B;

bool ToLeft ( const punct & A, const punct & B, const punct & C )
{
    return ( 1LL * B.y - A.y )*( C.x - B.x ) < (1LL* C.y - B.y )*( B.x - A.x );
}

bool comp( const punct & B, const punct & C )
{
    return ToLeft( P[1], B, C );
}
void Read()
{
    fin >> N;

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

vector < punct > S;

void Solve()
{
    int first = 1;

    for( int i = 2; i <= N; ++i )
        if( P[i].x < P[first].x || (P[i].x == P[first].x && P[i].y < P[first].y ) )
            first = i;

    swap( P[first], P[1] );

    sort ( P+2, P+N+1, comp );

    //for( int i = 1; i <= N; ++i )fout << P[i].x << ' ' << P[i].y << '\n';

    S.push_back( P[1] );
    S.push_back( P[2] );

    for( int i = 3; i <= N; ++i )
    {
        A = S[S.size()-1];
        B = S[S.size()-2];

        //cout << A.x << ' ' << A.y << ' ' << B.x << ' ' << B.y << ' ' << P[i].x << ' ' << P[i].y << ' ' << ToLeft ( B, A, P[i] ) << '\n';

        if( ToLeft ( B, A, P[i] ) == 1 )
            S.push_back( P[i] );
        else
        {
            while( ToLeft ( B, A, P[i] ) == 0 && i <= N)
            {
                S.pop_back();
                A = S[S.size()-1];
                B = S[S.size()-2];
                //cout << A.x << ' ' << A.y << ' ' << B.x << ' ' << B.y << '\n';
                ++i;
            }
            i--;
            if( i <= N ) S.push_back( P[i] );
        }
    }

    fout << S.size() << '\n';
    for( int i = 0; i < S.size() ; ++i )
        fout << fixed << setprecision( 6 ) << S[i].x << ' ' << S[i].y << '\n';

}
int main()
{
    Read();
    Solve();
    return 0;
}