Cod sursa(job #3247044)

Utilizator andrei0simionAndrei Simion andrei0simion Data 5 octombrie 2024 12:24:26
Problema Gradina Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>

using namespace std;

struct Punct
{
    int indexInitial = -1;

    long long x = 0;
    long long y = 0;

    int parte = -2;
    int parteIfasuratoare = -2;

    Punct() { }
    Punct(long long x, long long y)
    {
        this->x = x;
        this->y = y;
    }
};

bool SortareCoordonate(Punct a, Punct b)
{
    if (a.x < b.x || (a.x == b.x && a.y < b.y))
        return true;
    return false;
}

ifstream in("gradina.in");
ofstream out("gradina.out");

int nrPuncte;
Punct* puncte;

int nrElementeStiva;
int* stiva;

long long Arie(Punct a, Punct b, Punct c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}

long long InfasuratoareConvexa(int parte)
{
    int indexPrimulPunct = -1;
    for (int i = 0; i < nrPuncte; i++)
    {
        if (puncte[i].parte != parte)
            continue;
        indexPrimulPunct = i;
        break;
    }
    int indexUltimulPunct = -1;
    for (int i = nrPuncte - 1; i >= 0; i--)
    {
        if (puncte[i].parte != parte)
            continue;
        indexUltimulPunct = i;
        break;
    }
    if (indexUltimulPunct == -1 || indexUltimulPunct == indexPrimulPunct)
        return -1;

    for (int i = 0; i < nrPuncte; i++)
    {
        if (puncte[i].parte != parte)
            continue;

        long long arie = Arie(puncte[indexPrimulPunct], puncte[indexUltimulPunct], puncte[i]);
        if (arie < 0)
            puncte[i].parteIfasuratoare = -1;
        else
            puncte[i].parteIfasuratoare = 1;
    }
    puncte[indexPrimulPunct].parteIfasuratoare = 0;
    puncte[indexUltimulPunct].parteIfasuratoare = 0;

    bool punctInterior = false;
    nrElementeStiva = 0;

    for (int i = 0; i < nrPuncte; i++)
    {
        if (puncte[i].parte != parte || puncte[i].parteIfasuratoare > 0)
            continue;

        if (nrElementeStiva < 2)
        {
            stiva[nrElementeStiva] = i;
            nrElementeStiva++;
            continue;
        }

        if (nrElementeStiva >= 2 && Arie(puncte[stiva[nrElementeStiva - 2]], puncte[stiva[nrElementeStiva - 1]], puncte[i]) < 0)
        {
            punctInterior = true;
            break;
        }
        stiva[nrElementeStiva] = i;
        nrElementeStiva++;
    }
    if (punctInterior)
        return -1;

    nrElementeStiva--;
    int offset = nrElementeStiva;
    for (int i = nrPuncte - 1; i >= 0; i--)
    {
        if (puncte[i].parte != parte || puncte[i].parteIfasuratoare < 0)
            continue;

        if (nrElementeStiva < offset + 2)
        {
            stiva[nrElementeStiva] = i;
            nrElementeStiva++;
            continue;
        }

        if (nrElementeStiva >= offset + 2 && Arie(puncte[stiva[nrElementeStiva - 2]], puncte[stiva[nrElementeStiva - 1]], puncte[i]) < 0)
        {
            punctInterior = true;
            break;
        }
        stiva[nrElementeStiva] = i;
        nrElementeStiva++;
    }
    if (punctInterior || nrElementeStiva <= 2)
        return -1;

    nrElementeStiva--;
    long long ariePoligon = 0;
    for (int i = 1; i < nrElementeStiva - 1; i++)
    {
        ariePoligon += abs(Arie(puncte[stiva[0]], puncte[stiva[i]], puncte[stiva[i + 1]]));
    }

    return ariePoligon;
}

int main()
{
    in >> nrPuncte;

    puncte = new Punct[nrPuncte];
    for (int i = 0; i < nrPuncte; i++)
    {
        puncte[i].indexInitial = i;
        in >> puncte[i].x;
        in >> puncte[i].y;
    }
    sort(puncte, puncte + nrPuncte, SortareCoordonate);

    long long difAriiMinima = 1000000000000000000;
    string configuratieMinima = "";
    for (int i = 0; i < nrPuncte; i++)
        configuratieMinima += '-';

    stiva = new int[nrPuncte];
    for (int i = 0; i < nrPuncte; i++)
    {
        for (int o = 0; o < nrPuncte; o++)
        {
            for (int j = 0; j < nrPuncte; j++)
            {
                long long arie = Arie(puncte[i], puncte[o], puncte[j]);
                if ((arie < 0 && i < o) || (arie > 0 && i > o))
                    puncte[j].parte = -1;
                else
                    puncte[j].parte = 1;
            }
            puncte[i].parte = -1;
            puncte[o].parte = 1;

            long long ariePoligon1 = InfasuratoareConvexa(-1);
            if (ariePoligon1 == -1)
                continue;
            long long ariePoligon2 = InfasuratoareConvexa(1);
            if (ariePoligon2 == -1)
                continue;

            string configuratie = "";
            for (int i = 0; i < nrPuncte; i++)
                configuratie += '-';
            for (int i = 0; i < nrPuncte; i++)
            {
                if (puncte[i].parte == -1)
                    configuratie[puncte[i].indexInitial] = 'V';
                else
                    configuratie[puncte[i].indexInitial] = 'I';
            }
            if (configuratie[0] == 'V')
            {
                for (int i = 0; i < nrPuncte; i++)
                {
                    if (puncte[i].parte == -1)
                        configuratie[puncte[i].indexInitial] = 'I';
                    else
                        configuratie[puncte[i].indexInitial] = 'V';
                }
            }

            long long difArii = abs(ariePoligon2 - ariePoligon1);
            if (difArii <= difAriiMinima || (difArii == difAriiMinima && configuratie < configuratieMinima))
            {
                difAriiMinima = difArii;
                configuratieMinima = configuratie;
            }
        }
    }

    double arieReala = (double)difAriiMinima / 2;
    if ((long long)arieReala == arieReala)
        out << arieReala << ".0" << '\n';
    else
        out << arieReala << '\n';
    out << configuratieMinima << '\n';

    delete[] stiva;
    delete[] puncte;
    return 0;
}