Cod sursa(job #3339071)

Utilizator mariusharabariMarius Harabari mariusharabari Data 5 februarie 2026 23:52:54
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.31 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");

const int NMAX = 252;
const double EPS = 1e-9;
int n;
double dif = 1e9;
char fina[NMAX];

struct par{
    double x, y;
    int idx;
}v[NMAX];

double arie(par a, par b, par c){
    return a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
}

bool comp(par a, par b){
    if(abs(a.x - b.x) > EPS)
        return a.x < b.x;
    return a.y < b.y;
}

bool comp_idx(int a, int b){
    if(abs(v[a].x - v[b].x) > EPS)
        return v[a].x < v[b].x;
    return v[a].y < v[b].y;
}

double ariehull(vector<int> plan){
    if(plan.size() < 3) return 0;

    int m = plan.size();
    vector<int> jos, sus, hull;

    sort(plan.begin(), plan.end(), comp_idx);

    for(int i=0; i<m; i++){
        while(jos.size()>1 && arie(v[jos[jos.size()-2]], v[jos[jos.size()-1]], v[plan[i]]) <= 0)
            jos.pop_back();
        while(sus.size()>1 && arie(v[sus[sus.size()-2]], v[sus[sus.size()-1]], v[plan[i]]) >= 0)
            sus.pop_back();
        jos.push_back(plan[i]);
        sus.push_back(plan[i]);
    }


    if(jos.size() + sus.size() - 2 < m)
        return 0;

    for(int a : jos)
        hull.push_back(a);

    for(int i = sus.size()-2; i >= 1; i--)
        hull.push_back(sus[i]);

    double aria = 0;
    for(int i=0; i<hull.size(); i++){
        int j = (i+1) % hull.size();
        aria += v[hull[i]].x * v[hull[j]].y;
        aria -= v[hull[i]].y * v[hull[j]].x;
    }

    return abs(aria / 2.0);
}

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

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


    for(int i=1; i<n; i++){
        for(int j=1; j<=n; j++){
            if(i == j) continue;

            vector<int> plani, planj;
            plani.push_back(i);
            plani.push_back(j);

            for(int k=1; k<=n; k++){
                if(k == i || k == j)
                    continue;

                if(arie(v[i], v[j], v[k]) <= 0)
                    planj.push_back(k);
                else
                    plani.push_back(k);
            }

            double ariai = ariehull(plani);
            double ariaj = ariehull(planj);

            if(ariai == 0 || ariaj == 0)
                continue;

            double difa = abs(ariai - ariaj);

            if(difa < dif - EPS){
                dif = difa;
                for(int p : planj)
                    fina[v[p].idx] = 'V';
                for(int p : plani)
                    fina[v[p].idx] = 'I';
            }
            else if(abs(difa - dif) < EPS){
                char aux[NMAX];
                for(int p : planj)
                    aux[v[p].idx] = 'V';
                for(int p : plani)
                    aux[v[p].idx] = 'I';

                int poz = 1;
                while(poz <= n && aux[poz] == fina[poz])
                    poz++;

                if(poz <= n && aux[poz] == 'I'){
                    for(int p=1; p<=n; p++)
                        fina[p] = aux[p];
                }
            }
        }
    }

    fout << fixed << setprecision(1) << dif << '\n';
    for(int i=1; i<=n; i++)
        fout << fina[i];
    fout << '\n';

    return 0;
}