Cod sursa(job #1886980)

Utilizator EpictetStamatin Cristian Epictet Data 21 februarie 2017 11:52:50
Problema Gradina Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.64 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];
double dif, sol = 10000000000000;
char S[260], SSS[260];
pair < pair < int, int >, int > P[260], A1[260], B1[260], A2[260], B2[260];
bool F[260];

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

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

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

double 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;
        }
    }
    double 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';
                for (int k = 1; k <= n; k ++) SSS[k] = S[k];
                for (int k = 1; k <= a1; k ++) S[A1[k].second] = 'V';
                for (int k = 1; k <= b2; k ++) S[B2[k].second] = 'I';
                if (S < SSS) for (int k = 1; k <= n; k ++) SSS[k] = S[k];;
            }
            else if (dif == sol)
            {
                for (int k = 1; k <= a1; k ++) S[A1[k].second] = 'I';
                for (int k = 1; k <= b2; k ++) S[B2[k].second] = 'V';
                if (S < SSS) for (int k = 1; k <= n; k ++) SSS[k] = S[k];
                for (int k = 1; k <= a1; k ++) S[A1[k].second] = 'V';
                for (int k = 1; k <= b2; k ++) S[B2[k].second] = 'I';
                if (S < SSS) for (int k = 1; k <= n; k ++) SSS[k] = S[k];
            }
            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';
                for (int k = 1; k <= n; k ++) SSS[k] = S[k];
                for (int k = 1; k <= b1; k ++) S[B1[k].second] = 'V';
                for (int k = 1; k <= a2; k ++) S[A2[k].second] = 'I';
                if (S < SSS) for (int k = 1; k <= n; k ++) SSS[k] = S[k];
            }
            else if (dif == sol)
            {
                for (int k = 1; k <= b1; k ++) S[B1[k].second] = 'I';
                for (int k = 1; k <= a2; k ++) S[A2[k].second] = 'V';
                if (S < SSS) for (int k = 1; k <= n; k ++) SSS[k] = S[k];
                for (int k = 1; k <= b1; k ++) S[B1[k].second] = 'V';
                for (int k = 1; k <= a2; k ++) S[A2[k].second] = 'I';
                if (S < SSS) for (int k = 1; k <= n; k ++) SSS[k] = S[k];
            }
        }
    }
    fout << fixed << setprecision(1) << sol / 2 << '\n';
    fout << (S + 1) << '\n';
    fout.close();
    return 0;
}