Cod sursa(job #2610181)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 4 mai 2020 16:36:56
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.43 kb
#include <bits/stdc++.h>

using namespace std;

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

struct NANI
{
    int x, y;
};

NANI Ion[252];
NANI Vasile[252];

int st[252];

char ch[252];

NANI a[252];

double Min;

int n, aux;

int vfIon, vfVasile;

char S[252];

bool viz[252];

void Read ()
{
    f >> n;

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

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

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

    return true;
}

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

double convex_hull (NANI p[], int m)
{
    double sol = 0;
    for (int i = 1; i <= m; i++)
        viz[i] = false;

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

    int poz = 2;
    int pas = 1;

    while (viz[1] == false)
    {
        while (viz[poz] == true)
        {
            poz += pas;
            if (poz == m) pas = -1;
        }

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

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

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

    sol = sol / 2;

    if (vf != m + 1)
    {
        aux = 0;
    }

    return sol;
}

void Solve ()
{
    Min = 1000000000;

    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            vfIon = 0;
            vfVasile = 0;
            if (i == 1 || det(a[1], a[i], a[j]) < 0)
            {
                for (int k = 1; k <= n; k++)
                {
                    if (k == i || k == j || det(a[k], a[i], a[j]) < 0)
                    {
                        ch[k] = 'I';
                        vfIon++;
                        Ion[vfIon] = a[k];
                    }
                    else
                    {
                        ch[k] = 'V';
                        vfVasile++;
                        Vasile[vfVasile] = a[k];
                    }
                }
            }
            else
            {
                for (int k = 1; k <= n; k++)
                {
                    if (k == i || k == j || det(a[k], a[i], a[j]) < 0)
                    {
                        ch[k] = 'V';
                        vfVasile++;
                        Vasile[vfVasile] = a[k];
                    }
                    else
                    {
                        ch[k] = 'I';
                        vfIon++;
                        Ion[vfIon] = a[k];
                    }
                }
            }

            if (vfIon < 3 || vfVasile < 3) continue;

            sort(Ion + 1, Ion + vfIon + 1, cmp);
            sort(Vasile + 1, Vasile + vfVasile + 1, cmp);

            aux = 1;
            double dif = abs(convex_hull(Ion, vfIon) - convex_hull(Vasile, vfVasile));

            if (aux == 0) continue;

            if (dif < Min)
            {

                Min = dif;


                for (int k = 1; k <= n; k++) S[k] = ch[k];

            }
        }
    }

    g << setprecision(1) << fixed;

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

int main()
{
    Read();

    Solve();

    return 0;
}