Cod sursa(job #840474)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 22 decembrie 2012 18:59:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
using namespace std;
ifstream f ( "infasuratoare.in" );
ofstream g ( "infasuratoare.out" );
#include <algorithm>
#define LE 166600
#include <iomanip>
#include <vector>
pair<double, double> A[LE];
int ST[LE];
#define inf 1<<30
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;
    A[0] = make_pair ( inf, inf );

    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 ) if ( i != minim )
        {
            A[i].first -= A[minim].first;
            A[i].second -= A[minim].second;
        }


    swap ( A[minim], A[n--] );
    head = n + 1;

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

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

    for ( i = 2; 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 ( 13 );

    g << l << '\n';

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



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