Cod sursa(job #2371410)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 6 martie 2019 17:30:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>
#define N 120005
#define inf 1000000005

using namespace std;

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

struct punct
{
    double x, y;
};

int n;
punct A[N];

vector <punct> S;

void read()
{
    int i;

    fin >> n;

    for ( i = 1; i <= n; ++i )
         fin >> A[i].x >> A[i].y;

    fin.close();
}

bool comp( punct X, punct Y )
{
    return X.y < Y.y || X.y == Y.y && X.x < Y.x;
}

bool orientare1( punct X, punct Y )
{
    return ( X.y - A[1].y ) * ( Y.x - X.x ) < ( Y.y - X.y ) * ( X.x - A[1].x );
}

bool orientare( punct X, punct Y, punct Z )
{
    return ( Y.y - X.y ) * ( Z.x - Y.x ) < ( Z.y - Y.y ) * ( Y.x - X.x );
}

void solve()
{
    int i;

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

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

    for ( i = 3; i <= n; ++i )
    {
        while ( !orientare( S[S.size()-2], S[S.size()-1], A[i] ) )
               S.pop_back();
        S.push_back( A[i] );
    }

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

    /*int poz;
    punct mini;
    mini.x = mini.y = inf;

    for ( i = 0; i < S.size(); ++i )
         if ( S[i].y < mini.y || S[i].y == mini.y && S[i].x < mini.x )
         {
             mini = S[i];
             poz = i;
         }

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

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

int main()
{
    read();

    solve();

    fout.close();

    return 0;
}