Cod sursa(job #2609894)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 3 mai 2020 19:25:39
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

struct punct
{
    int x, y;
};
punct a[300];

int N;

punct ion[300];
punct vasile[300];

char car[300], sol[300];

bool viz[300];
int st[300];

void Read ()
{
    f >> N;

    for (int i = 1; i <= N; ++i)
        f >> a[i].x >> a[i].y;
}

bool cmp (punct a, punct b)
{
    if (a.x > b.x) return false;

    if (a.x == b.x && a.y > b.y) return false;

    return true;
}

int det (punct a, punct b, punct c)
{
    return (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y);
}

double Area (punct p[], int N)
{
    double sol = 0;

    sort(p+1, p+N+1, cmp);

    for (int i = 1; i <= N; ++i)
        viz[i] = false;

    st[1] = 1;
    st[2] = 2;
    viz[2] = true;

    int vf = 2;

    int poz = 2, pas = 1;

    while (viz[1] == false)
    {
        while (viz[poz] == true)
        {
            poz += pas;

            if (poz == N) pas = -1;
        }

        while (vf >= 2 && det(p[st[vf-1]], p[st[vf]], p[poz]) < 0)
        {
            viz[st[vf]] = 0;

            -- vf;
        }

        ++ vf;
        st[vf] = poz;
        viz[poz] = 1;
    }

    for (int i = 1; i < vf; ++i)
        sol = sol + det(p[0], p[st[i]], p[st[i+1]]);

    sol = sol / 2;

    return sol;
}

void Solve()
{
    double Min = 1000000000;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
        {
            if (i == j) continue;

            int nr_ion = 0, nr_vasile = 0;

            for (int k = 1; k <= N; ++k)
                if (det(a[i], a[j], a[k]) <= 0)
                {
                    vasile[++nr_vasile] = a[k];

                    car[k] = 'V';
                }
                else
                {
                    ion[++nr_ion] = a[k];

                    car[k] = 'I';
                }

            if (nr_vasile < 3 || nr_ion < 3) continue;

            double arie_ion = Area(ion, nr_ion);
            double arie_vasile = Area(vasile, nr_vasile);

            double dif = abs(arie_ion - arie_vasile);

            if (dif < Min)
            {
                Min = dif;

                for (int k = 1; k <= N; ++k)
                    sol[k] = car[k];
            }
            else if (dif == Min)
            {
                bool ok = 1;
                for (int k = 1; k <= N; ++k)
                    if (sol[k] > car[k]) break;
                    else if (sol[k] < car[k])
                    {
                        ok = 0;

                        break;
                    }

                if (ok == 1)
                {
                    for (int k = 1; k <= N; ++k)
                        sol[k] = car[k];
                }
            }
        }

    g << Min << '\n';
    for (int i = 1; i <= N; ++i)
        g << sol[i];
}

int main()
{
    Read();

    Solve();

    return 0;
}