Cod sursa(job #3338180)

Utilizator parrot279Sofi Tudose parrot279 Data 1 februarie 2026 12:03:35
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.67 kb
#include <bits/stdc++.h>

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

const int nmax = 255;
double arie(vector<int> a);
bool cmp2(int a, int b);

struct pct
{
    long long x, y;
    int id;
};
long long triunghi(pct a, pct b, pct c);
bool cmp(pct a, pct b);
pct v[nmax];

int n;
char sol[nmax];
double difmin = DBL_MAX;

int main()
{
    fin>>n;
    for(int i = 1; i <= n; ++i)
    {
        fin>>v[i].x>>v[i].y;
        v[i].id = i;
        sol[i] = 'V';
    }


    sort(v+1, v+n+1, cmp);

    for(int i = 1; i < n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(i == j)
                continue;
            vector<int> ion, vasile;
            ion.push_back(i);
            ion.push_back(j);

            for(int k = 1; k <= n; ++k)
            {
                if(k == i || k == j)
                    continue;
                if(triunghi(v[i], v[j], v[k]) <= 0)
                    vasile.push_back(k);
                else
                    ion.push_back(k);
            }
            double arievasile = arie(vasile), arieion = arie(ion);

            if(arievasile == 0 || arieion == 0)
                continue;

            if(abs(arievasile - arieion) < difmin)
            {
                difmin = abs(arievasile - arieion);
                for(auto poz : vasile)
                    sol[v[poz].id] = 'V';
                for(auto poz : ion)
                    sol[v[poz].id] = 'I';
            }
            else if(abs(arievasile - arieion) == difmin)
            {
                char aux[nmax];

                for(auto poz : vasile)
                    aux[v[poz].id] = 'V';
                for(auto poz : ion)
                    aux[v[poz].id] = 'I';

                int ind = 1;
                while(aux[ind] == sol[ind] && ind <= n)
                    ++ind;
                if(ind <= n && aux[ind] == 'I')
                {
                    for(int i = 1; i <= n; ++i)
                        sol[i] = aux[i];
                }
            }
        }
    }
    fout<<fixed<<setprecision(1)<<difmin<<"\n";
    for(int i = 1; i <= n; ++i)
        fout<<sol[i];





    return 0;
}

double arie(vector<int> a)
{
    if(a.size() < 3)
        return 0;

    int nr = a.size(), cntsus = 0, cntjos = 0;
    vector<int> sus, jos, ch;

    sort(a.begin(), a.end(), cmp2);

    for(int i = 0; i < nr; ++i)
    {
        while(cntsus >= 2 && triunghi(v[sus[cntsus-2]], v[sus[cntsus-1]], v[a[i]]) >= 0)
        {
            --cntsus;
            sus.pop_back();
        }
        while(cntjos >= 2 && triunghi(v[jos[cntjos-2]], v[jos[cntjos-1]], v[a[i]]) <= 0)
        {
            --cntjos;
            jos.pop_back();
        }
        ++cntsus;
        ++cntjos;
        sus.push_back(a[i]);
        jos.push_back(a[i]);
    }

    if(cntsus + cntjos - 2 < nr)
        return 0;

    for(int i = 0; i < cntjos; ++i)
        ch.push_back(jos[i]);
    for(int i = cntsus - 2; i >= 1; --i)
        ch.push_back(sus[i]);

    long long ans = 0;

    ans += v[ch[nr-1]].x * v[ch[0]].y - v[ch[nr-1]].y * v[ch[0]].x;
    for(int i = 0; i < nr-1; ++i)
    {
        ans += v[ch[i]].x * v[ch[i+1]].y - v[ch[i]].y * v[ch[i+1]].x;
    }
    return abs(ans) / 2.0;
}

long long triunghi(pct a, pct b, pct c)
{
    return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
}

bool cmp2(int a, int b)
{
    if(v[a].x == v[b].x)
        return (v[a].y < v[b].y);
    return (v[a].x < v[b].x);
}

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