Cod sursa(job #2844428)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 4 februarie 2022 15:20:18
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 9.37 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n;
char aux[255], afis[255];

struct coords {
    int x, y, ind;
}v[255], a[255], b[255];

bool cmp(coords a, coords b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

long long sp(coords a, coords b, coords c)
{
    return 1LL * (b.x - a.x) * (c.y - a.y) - 1LL * (c.x - a.x) * (b.y - a.y);
}

long long check(coords pct[], int len)
{
    int nr_elem = 0;
    coords stiva[255];
    for(int i = 1; i <= len; i++)
    {
        while(nr_elem > 1 && sp(stiva[nr_elem - 1], stiva[nr_elem], pct[i]) < 0)
            nr_elem--;
        stiva[++nr_elem] = pct[i];
    }
    int cnt = nr_elem;
    for(int i = len - 1; i >= 1; i--)
    {
        while(nr_elem > cnt && sp(stiva[nr_elem - 1], stiva[nr_elem], pct[i]) < 0)
        {
            nr_elem--;
        }
        stiva[++nr_elem] = pct[i];
    }

    if(nr_elem - 1 != len)
        return -1;
    if(sp(stiva[nr_elem - 2], stiva[nr_elem - 1], pct[1]) < 0)
        return -1;
    long long arie = 0;
    for(int i = 1; i < nr_elem; i++)
        arie = arie + (stiva[i].x * stiva[i+1].y - stiva[i+1].x * stiva[i].y);
    return abs(arie);
}

bool strcompare(char s1[], char s2[])
{
    for(int i = 1; i <= n; i++)
        if(s1[i] > s2[i])
            return 0;
    return 1;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i].x >> v[i].y;
        v[i].ind = i;
    }
    sort(v + 1, v + n + 1, cmp);
    check(v, n);
    long long solmin =(1LL << 50);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            int cnta = 0, cntb = 0;
            if(i==j)
                continue;
            for(int k = 1; k <= n; k++)
            {
                if(k == i)
                {
                    a[++cnta] = v[k];
                    aux[v[k].ind] = 'I';
                    continue;
                }
                if(k == j)
                {
                    b[++cntb] = v[k];
                    aux[v[k].ind] = 'V';
                    continue;
                }
                if((sp(v[i], v[j], v[k]) < 0) == (i > j))
                {
                    a[++cnta] = v[k];
                    aux[v[k].ind] = 'I';
                }
                else
                {
                    b[++cntb] = v[k];
                    aux[v[k].ind] = 'V';
                }
            }
            if(cnta >=3 && cntb >= 3)
            {
                long long ariea = check(a, cnta);
                long long arieb = check(b, cntb);
                if(ariea >= 0 && arieb >= 0)
                {
                    long long diff = abs(ariea - arieb);
                    if(diff <= solmin)
                    {
                        if(diff < solmin)
                        {
                            solmin = diff;
                            for(int i = 1; i <= n; i++)
                                afis[i] = aux[i];
                        }
                        else if(strcompare(aux, afis) == 1)
                            for(int i = 1; i <= n; i++)
                                afis[i] = aux[i];
                    }
                }
            }
        }
    }
    fout << solmin / 2;
    if(solmin % 2 == 0)
        fout << ".0";
    else fout <<".5";
    fout << '\n';
    if(afis[1] == 'V')
        for(int i = 1; i <= n; i++)
            afis[i] = 'V' + 'I' - afis[i];
    for(int i = 1; i <= n; i++)
        fout << afis[i];
    return 0;
}

/*
                                          .::////++ossss+.  `++:``
                                         -md+ohddhhhhhhMM/  oMMMNds+-`
                                  `/dh`  /M:  `::://///mMo `hMm+oydmmNhs/-`
                                `:hNNM/  /M+   -:://///hMh `mMy/////+oydMNd`
                              `/dNmsoMd` :Mm.`.-:://///yMd`.MM+////////oNMy`
                            `/hNms///dM: :MN/--::::////oMm.-MN/////////dMN-
                          `/hNms/////oMd`-NN+::::::////+mNhhMh////////oMMo
                          yMNy////////dMhdNm/:::::://////+oss/////////mMm.
                          /NNs////////oddyo/::::::://////////////////sMM+
                          `+NMs//////////::::::::::://///////////////mMh`
                           `+NMs//////////::::::::::////////////////sMN:
                            `+MNo/////////::::::::::////////////////mMs`
                             `+MNo/////////:::::::::///////////////sMm.
                               oMN+////////:::::::::///////////////NM/
                                oMm+/////////+ooooosssssssssooo+//yMh
                                `oMm+////+osssssssssssssssssssssssNN.
                                 `oMm+/osssssssssssssssssssssssssdM/
                                  `+NmysssssssssssssssssssssssshNMs
                                    -hMmhyssssssssssssssssyhdNNho-`
                                     `-ohmNmmdddddddmmmmmhys+-``
                                        ``.-:://///::-..```
                                           ````..--:://++oosyyhh+`
                             ```    .+osyyhdmmmmmmmmmmddddhyyshMM/
                           -sdmdy. -dMdhyyysooo+++/////::///:::yMm--os+-`
                          .dMMMMm-/mMmyhddd+::::::::::::omNmmdyohMmNMMMNo
                          +MMMMMNmMMMMMMMMMs::::::::::::sMMMMMMMNMMMMMMMm.
                          oMMMMMMMMMMMMMMNd/::::::::::::+mNMMMMMMMMMMMMMM:
                          /NMMMMMMMMNNmdyo/:::::/+++/::::/ohmmNMMMMMMMMMN-
                          `+hmNNdhyso+/::::::++:+ooo/::+::::/+oyhdmNNNNNy`
                            :mMy/:::::::::::/M+::::::::y::::::::://+oNMs`
                          `/NNs:/shhs/::::::+M:::::::::y:::::::/+//::sMm-
                    ``````oNNo:oNMMMMNy:::::+M:::::::::y:::::+hNMMmo::hMh`     ````
                `.:oydddhhMm+:/yyyhmMMMy::::+M:::::::::y::::sNMMMMMMo:/dMs``/oosssso/-`
              `+hNMNNNNNNNm/:::::://+ymN/:::+N:::::::::y:::sNmhso++sy::/mM+sMNNNNNNNNNh-
              +MMNNNNNNNNNd/::::::+sso:o::::+N:::::::::y:::+/+ss+:::::::+NMNNNNNNNNNNNMy
              +MMNNNNNNNNNNs::::::::::+ooo/:/+:::::::::dyyssso:::::::::::oNNNNNNNNNNNNMh
              -MMMNNNNNNNNNmdddhhhyyyNds//:::::::::::::///+sdNmhhhhhhhddddNNNNNNNNNNNNMo
              `dMMMMMMNNNNNNNNNNNNNNMm/::::::::::::::::::::::/mMNNNNNNNNNNNNNNNNNNMMMMN-
               :NMMMMMMMMMMMMMMMMMMMMMmyo+//:::::::::::::://+odMMMMMMMMMMMMMMMMMMMMMMM+`
                +MNNmNMMMMMMMMMMMMMMMMMMMMNNNNmddhhhhhddmNNNMMMMMMMMMMMMMMMMMMMMMMMNd/`
               :mMdh/.-::/+ooosssyyyhhhhhhhhhddddddddddddddddddddhhhyyssooo+/:ydmMMm.
             `oNMNhhy:           ``      ``````````````````````````         `+hhhNMMm/`
            -hMMNmhhhyo.         ``               `              ``        -shhhhmNMMNs`
          `+mMMNNmhhhhhyo-`      ``               .              ``     .:shhhhhhmNNNMMh.
         .yMMNNNNmhhhhhhhhs+-.`  ``               .              `  `-/oyhhhhhhhhmNNNNMMd:
        :dMMNNNNNmhhhhhhhhhhhyso/:-.``            `         ``..-/+oyyhhhhhhhhhhhNNNNNNMMN+
      `+NMMNNNNNNmhhhhhhhhhhhhhhhhyyssso+++//////://///+++osssyyhhhhhhhhhhhhhhhhhNNNNNNMMMN-
     `sMMMMMNNNNNNhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhdNNNNNMMMMMs
     .MMMMMMMMNNNNdhhhhhhhhhhhhhhhhhhhhhhhhhhhdddhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhmNNNMMMMMMN:
     `+NMMMMMMMNNNmhhhhhhhhhhhhhhhhhhhhhhddmmmmmdhhhmmmmmdhhhhhhhhhhhhhhhhhhhhhdNNNMMMMMMm:
       .yNMMMMMMMNNd/syhhhhhhhhhhhhhhhhdmmmmmmmdhhhhdmmmmdhsssssyyhhhhhhhhhhyyomNNMMMMMMh.
         :dMMMMMMMMNs`.+shhhhhhhhhhysssssssyyhhhhhhhmmdysssssssssssyhhhhhhs/.`hNMMMMMMMs`
          `+NMMMMMMMMh.  .:+syhhhhsssssssssssssssshddssssssssssssssshys+:`  `hMMMMMMMN/`
            .sMMMMMMMMN/     `-:+oooosssssssssssssssssssssssooo+//:-.`     -mMMMMMMMM/
              :MMMMMMMMMd:     `    ```....-----------...````      `     `sNMMMMMMMNMd`
             `sMMmMMMMMMMMh/`                                          .oNMMMMMMMNdhMM+
             /MMmyhmMMMMMMMMmo-                  ``                 `:sNMMMMMMMNdhyymMN-
            .mMmyyyyhmNMMMMMMMNdo:`              ``              `:odNMMMMMMMNdhyyyyyNMh`
           `hMMysyyyyyhdNMMMMMMMMNmy+:.`         ``         `.:+hmNMMMMMMMMNdhyyyyssshMMo
           oMMhssssyyyyyyhdNMMMMMMMMMNNmhs+/:---.-----://oyhmNNMMMMMMMMMNmhhyyyyysssssdMN:
          :NMdsssssssyyyyyyhhmNMMMMMMMMMMMMMMNNNNmNNNNNMMMMMMMMMMMMMMMNdhyyyyyysssssssyNMd`
         .mMNmdhyssssssyyyyyyyhdmNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNmhhyyyyyssssssssyyhNMMo
        `yMNyyhdmmhyssssssyyyyyyyhhdmMMMMMMMMMMMMMMMMMMMMMMMMMMMmdhhyyyyyyssssssyyhmmdhyhMN-
        +MMdsssssyhddhyysssssyyyyyyooshmNMMMMMMMMMMMMMMMMMMMNmhsooyyyyysssssyyddmmhyyssssmMd`
       -NMmsssssssssyyhddhyyssssyysooooosydNNMMMMMMMMMMMMNdysooooosysssyyhdmmdhysssssssssyNMo
      `dMNyssssssssssssssyhhdhhyys++++ooooooshmNMMMMMNmhsoooooo++++yhddddhyysssssssssssssshMN-
     `sMMhsssssssssssssssssssyyhhdhysoooooooooooyhddysoooooooosyyhhhhyyssssssssssssssssssssmMd`
     /MMmssssssssssssssssssssssssssyyhhdddddhhhhyyyhyyyhhhhhhhyysssssssssssssssssssssssssssyMMo`
    -NMNysssssssssssssssssssssssssssssssssssyyyhhhhyyyysssssssssssssssssssssssssssssssssssssdMN-
    /sso/////////////////////////////////////////////////////////////////////////////////////ss/
*/