Cod sursa(job #1785156)

Utilizator enacheionutEnache Ionut enacheionut Data 20 octombrie 2016 21:53:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define MAX_NUMAR_PUNCTE 120005

using namespace std;

vector<pair<double, double>> puncte(MAX_NUMAR_PUNCTE, make_pair(0.0, 0.0));
vector<pair<double, double>> stiva(MAX_NUMAR_PUNCTE, make_pair(0.0, 0.0));
int numarPuncte;
int varfStiva;

void CitireInput()
{
    ifstream in("infasuratoare.in");
    in>> numarPuncte;

    for( int i = 1; i<=numarPuncte; ++i )
    {
        in>> puncte[i].first>> puncte[i].second;
    }
    in.close();
}

int AlegerePunctStart()
{
    int indexElementMinim = 1;
    for( int i = 2; i<=numarPuncte; ++i )
    {
        if( puncte[i] < puncte[indexElementMinim] )
        {
            indexElementMinim = i;
        }
    }
    return indexElementMinim;
}

double ArieTriunghi(pair<double, double> punct1, pair<double, double> punct2,
                    pair<double, double> punct3)
{
    return punct1.first*punct2.second + punct2.first*punct3.second +
            punct3.first*punct1.second - punct3.first*punct2.second -
            punct1.first*punct3.second - punct2.first*punct1.second;
}

bool CompararePuncte(pair<double, double> punct1, pair<double, double> punct2)
{
    return ArieTriunghi(puncte[1], punct1, punct2) < 0;
}

void SortarePuncte()
{
    int indexElementMinim = AlegerePunctStart();

    swap(puncte[1], puncte[indexElementMinim]);
    sort(puncte.begin() + 2, puncte.begin() + numarPuncte + 1, CompararePuncte);
}

void ConvexHull()
{
    SortarePuncte();

    stiva[1] = puncte[1];
    stiva[2] = puncte[2];
    varfStiva = 2;
    for( int i = 3; i<=numarPuncte; ++i )
    {
        while( varfStiva >= 2 && ArieTriunghi(stiva[varfStiva - 1], stiva[varfStiva], puncte[i]) > 0 )
        {
            --varfStiva;
        }
        stiva[++varfStiva] = puncte[i];
    }
}

void AfisareRezultat()
{
    ofstream out("infasuratoare.out");
    out<< fixed<< varfStiva<< "\n";
    for( int i = varfStiva; i >= 1; --i )
    {
        out<< setprecision(12)<< stiva[i].first<<" "<< stiva[i].second<< "\n";
    }
    out.close();
}

int main()
{
    CitireInput();

    ConvexHull();

    AfisareRezultat();

    return 0;
}