Cod sursa(job #1984461)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 24 mai 2017 22:37:16
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.63 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <stack>
#include <iomanip>

#define ll long long
#define ld long double
#define pb push_back

using namespace std;

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

const int NLIM = 120000 + 10;

struct coordS
{
    ld x, y;
};

int N;
coordS pont[NLIM];


ld dist2( coordS p1, coordS p2 )
{
    return ( p2.x - p1.x ) * ( p2.x - p1.x ) + ( p2.y - p1.y ) * ( p2.y - p1.y );
}


int orient( coordS p1, coordS p2, coordS p3 )
{
    ld val = ( p2.y - p1.y ) * ( p3.x - p2.x ) - ( p3.y - p2.y ) * ( p2.x - p1.x );

    if( val < 0 )
        return -1;// left
    if( val > 0 )
        return 1;// right

    return 0;
}

int compar( const void* a, const void* b )
{
    coordS p1 = *(coordS*)a;
    coordS p2 = *(coordS*)b;

    // -1 ha left
    // 1 ha right

    int ori = orient( pont[0], p1, p2 );
    if( ori )
        return ori;
    // dist compar if collinear
    if( dist2( pont[0], p1 ) > dist2( pont[0], p2 ) ) return 1;
    if( dist2( pont[0], p1 ) < dist2( pont[0], p2 ) ) return -1;
    return 0;
}


int main()
{
    int st = 0;

    fin >> N;
    for( int i = 0; i < N; ++i )
    {
        fin >> pont[i].x;
        fin >> pont[i].y;

        if( pont[i].x < pont[st].x || ( pont[i].x == pont[st].x && pont[i].y < pont[st].y ) )
            st = i;
    }

    coordS emp = pont[st];
    pont[st] = pont[0];
    pont[0] = emp;

    qsort( pont + 1, N - 1, sizeof( coordS ), compar );
/*/
    for( int i = 0; i < N; ++i )
    {
        cerr << i << ": " <<  pont[i].x << " " << pont[i].y << "\n";
    }
//*/
    stack< int > res;

    res.push( 0 );
    res.push( 1 );

    //cout << orient()

    for( int i = 2; i < N; ++i )
    {
        bool megy = 1;
        while( megy )
        {
            megy = 0;
            int i2 = res.top();
            res.pop();
            int i1 = res.top();
            int ori = orient( pont[i1], pont[i2], pont[i] );

            // left
            if( ori == -1  || ori == 0 )
            {
                res.push( i2 );
            }
            // right
            else if( ori == 1 )
            {
                megy = 1;
            }
        }
        res.push( i );
    }

    fout << res.size() << "\n";
    stack< int > resrev;
    while( res.size() )
    {
        resrev.push( res.top() );
        res.pop();
    }

    while( resrev.size() )
    {
        fout << fixed << setprecision( 20 ) <<  pont[resrev.top()].x << " " << pont[resrev.top()].y << "\n";
        resrev.pop();
    }

    return 0;
}