Cod sursa(job #2263550)

Utilizator MelacasKorian Ebraahim Melacas Data 18 octombrie 2018 19:36:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.66 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct punct2D
{
    double x, y;
}punctCmp;

double testOrientare(const punct2D &a, const punct2D &b, const punct2D &c)
{
    return (double)(b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp(punct2D &a, punct2D &b)
{
    return (testOrientare(punctCmp,a,b) > 0);
}

class Stiva
{
    private :

    int nrElemente;
    punct2D* elemente;

    public :

    Stiva()
    {
        nrElemente = 0;
        elemente = new punct2D[120001];
    }
    bool add(const punct2D &nr)
    {
        elemente[nrElemente] = nr;
        nrElemente++;
        return 1;
    }
    bool removeElement()
    {
        if (nrElemente == 0)
            return 0;

        nrElemente--;
        return 1;
    }
    int getNumberOfElements()
    {
        return nrElemente;
    }
    bool afisareStiva(FILE* &afisare)
    {
        for (int i = 0 ; i < nrElemente ; i++)
            fprintf(afisare,"%lf %lf\n",elemente[i].x,elemente[i].y);

        return 1;
    }
    punct2D getPoint(const int &i)
    {
        return elemente[i - 1];
    }
};

int main()
{
    FILE* citire = fopen("infasuratoare.in","r");
    FILE* afisare = fopen("infasuratoare.out","w");

    int n(0);
    fscanf(citire,"%d\n",&n);

    punct2D* puncte = new punct2D[n + 1];
    int pctCmp(1);
    for (int i = 1 ; i <= n ; i++)
    {
        fscanf(citire,"%lf %lf",&puncte[i].x,&puncte[i].y);

        /// punctCompar trebuie sa fie cel mai de jos punct, stanga in caz de egalitate
        if (puncte[i].y < puncte[pctCmp].y)
                pctCmp = i;
        else if (puncte[i].y == puncte[pctCmp].y)
        {
            if (puncte[i].x < puncte[pctCmp].x)
                pctCmp = i;
        }
    }

    {
        punct2D aux;
        aux = puncte[pctCmp];
        puncte[pctCmp] = puncte[1];
        puncte[1] = aux;

        punctCmp = puncte[1];
    }

    sort(puncte + 2, puncte + n + 1,cmp);

    Stiva stiva;
    stiva.add(puncte[1]);
    stiva.add(puncte[2]);

    for (int i = 3 ; i <= n ; i++)
    {
        punct2D a = stiva.getPoint(stiva.getNumberOfElements() - 1);
        punct2D b = stiva.getPoint(stiva.getNumberOfElements());

        while(testOrientare(a,b,puncte[i]) <= 0 && stiva.getNumberOfElements() > 1)
        {
            stiva.removeElement();
            a = stiva.getPoint(stiva.getNumberOfElements() - 1);
            b = stiva.getPoint(stiva.getNumberOfElements());
        }
        stiva.add(puncte[i]);
    }
    fprintf(afisare,"%d\n",stiva.getNumberOfElements());
    stiva.afisareStiva(afisare);


    return 0;
}