Cod sursa(job #2664889)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 29 octombrie 2020 17:40:18
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.96 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 120005;
const int INF = 2000000000;

int N;
vector <pair<double, double> > V;

void Read() {
    fin >> N;

    for( int i = 1; i <= N; ++i ) {
        double x, y;

        fin >> x >> y;

        V.push_back( { x, y } );
    }
}

bool Clockwise( double x1, double y1, double x2, double y2, double x3, double y3 ) {
    return ( y1 - y2 ) * ( x2 - x3 ) > ( x1 - x2 ) * ( y2 - y3 );
}

bool Bigger( int a, int b ) {
    return Clockwise( V[0].first, V[0].second, V[a].first, V[a].second, V[b].first, V[b].second );
}

int Pivot( int lf, int rg ) {
    int steplf = 1, steprg = 0;

    while( lf < rg ) {
        if( Bigger( lf, rg ) ) {
            swap( V[lf], V[rg] );
            swap( steplf, steprg );
        }
        lf += steplf;
        rg -= steprg;
    }

    return lf;
}

void QuickSort( int lf, int rg ) {
    if( lf > rg ) return;

    int p = Pivot( lf, rg );

    QuickSort( lf, p - 1 );
    QuickSort( p + 1, rg );
}

void Do() {
    double xmin, ymin;
    int p;

    xmin = ymin = INF;

    for( int i = 0; i < V.size(); ++i )
        if( V[i].first < xmin ) { p = i; xmin = V[i].first; ymin = V[i].second; }
        else
            if( V[i].first == xmin && V[i].second <= ymin ) {
                xmin = V[i].first;
                ymin = V[i].second;
                p = i;
            }

    swap( V[0], V[p] );

    QuickSort( 1, N - 1 );

    //for( int i = 0; i < N; ++i )
    //    fout << V[i].first << ' ' << V[i].second << '\n';

    vector < pair<double, double> > stk;

    stk.push_back( V[0] );
    stk.push_back( V[1] );

    for( int i = 2; i < N; ++i ) {
        double x1 = stk[stk.size() - 2].first;
        double y1 = stk[stk.size() - 2].second;
        double x2 = stk[stk.size() - 1].first;
        double y2 = stk[stk.size() - 1].second;
        double x3 = V[i].first;
        double y3 = V[i].second;

        int steps = 0;

        //if( i == 6 ) fout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << '\n';

        while( Clockwise( x1, y1, x2, y2, x3, y3 ) ) {

           // fout << "***\n" << x3 << ' ' << y3 << '\n';

            stk.pop_back();
            ++steps;

            x1 = stk[stk.size() - 2].first;
            y1 = stk[stk.size() - 2].second;
            x2 = stk[stk.size() - 1].first;
            y2 = stk[stk.size() - 1].second;

            //fout << Clockwise( x1, y1, x2, y2, x3, y3 ) << '\n';

            //if( steps > 1 ) break;
        }

        stk.push_back( V[i] );
    }

    //fout << Clockwise( 4, 4, 1, 3, 2, 6 ) << '\n';

    fout << stk.size() << '\n';

    for( int i = 0; i < stk.size(); ++i )
        fout << fixed << setprecision(12) << stk[i].first << ' ' << stk[i].second << '\n';

}

int main()
{
    Read();
    Do();

    return 0;
}