Cod sursa(job #1886922)

Utilizator EpictetStamatin Cristian Epictet Data 21 februarie 2017 11:26:54
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <fstream>
#include <cstring>
#include <iomanip>
#include <algorithm>

using namespace std;

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

int n, a1, b1, a2, b2, V[260];
float dif, sol = 100000;
char S[260];
pair < pair < int, int >, int > P[260], A1[260], B1[260], A2[260], B2[260];
bool F[260];

int Cross_Product(pair < int, int > a, pair < int, int > b, pair < int, int > c)
{
    return (c.first - a.first) * (b.second - a.second) - (c.second - a.second) * (b.first - a.first);
}

int Sup(pair < int, int > a, pair < int, int > b)
{
    return (a.first * b.second) - (a.second * b.first);
}

float Modul(float a)
{
    return (a < 0 ? -a : a);
}

float Verif(pair < pair < int, int >, int > C[], int nr)
{
    memset(F, false, sizeof(F));
    V[1] = 1;
    V[2] = 2;
    V[0] = 2;
    F[1] = F[2] = true;
    for (int i = 1, p = 1; i > 0; i += (p = (i == nr ? -p : p)))
    {
        if (!F[i])
        {
            while (V[0] > 1 && Cross_Product(C[V[V[0] - 1]].first, C[V[V[0]]].first, C[i].first) > 0)
            {
                F[V[V[0] --]] = false;
            }
            V[++ V[0]] = i;
            F[i] = true;
        }
    }
    float arie = 0;
    V[nr + 1] = V[1];
    for (int i = 1; i <= nr; i ++)
    {
        arie += Sup(C[V[i]].first, C[V[i + 1]].first);
    }
    return Modul(arie);
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i ++)
    {
        fin >> P[i].first.first >> P[i].first.second;
        P[i].second = i;
    }
    sort(P + 1, P + 1 + n);
    for (int i = 1; i <= n; i ++)
    {
        for (int j = i + 1; j <= n; j ++)
        {
            a1 = b1 = a2 = b2 = 0;
            for (int k = 1; k <= n; k ++)
            {
                if (k == i)
                {
                    A1[++ a1] = P[k];
                    B1[++ b1] = P[k];
                }
                else if (k == j)
                {
                    A2[++ a2] = P[k];
                    B2[++ b2] = P[k];
                }
                else if (Cross_Product(P[i].first, P[k].first, P[j].first) > 0)
                {
                    A1[++ a1] = P[k];
                    A2[++ a2] = P[k];
                }
                else
                {
                    B1[++ b1] = P[k];
                    B2[++ b2] = P[k];
                }
            }
            dif = Modul(Verif(A1, a1) - Verif(B2, b2));
            if (dif < sol)
            {
                sol = dif;
                for (int k = 1; k <= a1; k ++) S[A1[k].second] = 'I';
                for (int k = 1; k <= b2; k ++) S[B2[k].second] = 'V';
            }
            dif = Modul(Verif(B1, b1) - Verif(A2, a2));
            if (dif < sol)
            {
                sol = dif;
                for (int k = 1; k <= b1; k ++) S[B1[k].second] = 'I';
                for (int k = 1; k <= a2; k ++) S[A2[k].second] = 'V';
            }
        }
    }
    fout << fixed << setprecision(1) << sol / 2 << '\n';
    fout << (S + 1) << '\n';
    fout.close();
    return 0;
}