Cod sursa(job #840493)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 22 decembrie 2012 19:52:48
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
using namespace std;
ifstream f ( "infasuratoare.in" );
ofstream g ( "infasuratoare.out" );
#include <algorithm>
#define LE 166600
#include <iomanip>
#include <vector>
#define double long double
pair<double, double> A[LE];
int ST[LE];
int i, n, head, minim, l;

inline double cross_product ( pair<double, double> IN, pair<double, double> P1, pair<double, double> P2 )
{
    return ( P1.first - IN.first ) * ( P2.second - IN.second ) - ( P1.second - IN.second ) * ( P2.first - IN.first );
}
bool comp ( pair<double, double> P1, pair<double, double> P2 )
{
    return P1.first * P2.second < P2.first * P1.second;
}
int main()
{
    f >> n;
minim=1;

    for ( i = 1; i <= n; ++i )
    {
        f >> A[i].first >> A[i].second;

        if ( A[i].second < A[minim].second || ( A[i].second == A[minim].second && A[i].first < A[minim].first ) )
            minim = i;
    }

    pair<double, double>needAdd = A[minim];

    for ( i = 1; i <= n; ++i )
        {
            A[i].first -= needAdd.first;
            A[i].second -= needAdd.second;
        }


    swap ( A[minim], A[1] );



    sort ( A + 2, A + n + 1, comp );

    ST[1] = 1;
    ST[2] = 2;
    l = 2;

    for ( i = 3; i <= n; ++i )
    {
        while  ( cross_product ( A[ST[l-1]], A[ST[l]], A[i] ) >= 0 && l >= 2 )
            --l;

        ST[++l] = i;
    }

    int okz = 0;

    while  ( l >= 2 &&  cross_product ( A[ST[l-1]], A[ST[l]], A[1] ) >= 0 )
    {
        --l;
        okz = 1;
    }

    if ( okz == 1 ) ++l;

    g << fixed;
    g << setprecision ( 12 );

    g << l << '\n';

    for ( i = l; i >=1; --i )
        g << A[ST[i]].first + needAdd.first << " " << A[ST[i]].second + needAdd.second << '\n';



    f.close();
    g.close();
    return 0;
}