Cod sursa(job #3339070)

Utilizator mariusharabariMarius Harabari mariusharabari Data 5 februarie 2026 23:46:09
Problema Gradina Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.55 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;
bitset <NMAX> ion, fina;

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;
}

vector <int> convexhull(vector <int> plan){
    int m = plan.size();
    if(m < 3) return plan;

    vector <int> jos, sus, rez;

    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]);
    }

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

    if(sus.size() > 1){
        sus.pop_back();
        reverse(sus.begin(), sus.end());
        sus.pop_back();
        for(int a : sus)
            rez.push_back(a);
    }

    return rez;
}

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

    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);
}

bool verificare(vector<int>& plani, vector<int>& planj){
    vector<int> hulli = convexhull(plani);
    vector<int> hullj = convexhull(planj);

    if(hulli.size() != plani.size() || hullj.size() != planj.size())
        return false;

    // Verifică separare cu muchii din hull Ion
    for(int i=0; i<hulli.size(); i++){
        int j = (i+1) % hulli.size();
        par a = v[hulli[i]];
        par b = v[hulli[j]];

        bool ok_vasile = true;
        bool ok_ion = true;

        for(int p : hullj){
            if(arie(a, b, v[p]) > -EPS){
                ok_vasile = false;
                break;
            }
        }

        for(int p : hulli){
            if(p == hulli[i] || p == hulli[j]) continue;
            if(arie(a, b, v[p]) < EPS){
                ok_ion = false;
                break;
            }
        }

        if(ok_vasile && ok_ion)
            return true;
    }


    for(int i=0; i<hullj.size(); i++){
        int j = (i+1) % hullj.size();
        par a = v[hullj[i]];
        par b = v[hullj[j]];

        bool ok_ion = true;
        bool ok_vasile = true;

        for(int p : hulli){
            if(arie(a, b, v[p]) > -EPS){
                ok_ion = false;
                break;
            }
        }

        for(int p : hullj){
            if(p == hullj[i] || p == hullj[j]) continue;
            if(arie(a, b, v[p]) < EPS){
                ok_vasile = false;
                break;
            }
        }

        if(ok_ion && ok_vasile)
            return true;
    }

    return false;
}

void backtrack(int poz, bitset<NMAX>& conf, vector<int>& plani, vector<int>& planj){
    if(poz > n){
        if(plani.size() < 3 || planj.size() < 3)
            return;

        if(!verificare(plani, planj))
            return;

        double ariai = ariehull(convexhull(plani));
        double ariaj = ariehull(convexhull(planj));
        double difa = abs(ariai - ariaj);

        if(difa < dif - EPS){
            dif = difa;
            fina = conf;
        } else if(abs(difa - dif) < EPS){
            bool mai_bun = false;
            for(int i=1; i<=n; i++){
                if(conf[i] != fina[i]){
                    mai_bun = (conf[i] > fina[i]);
                    break;
                }
            }
            if(mai_bun){
                fina = conf;
            }
        }
        return;
    }

    // Pune în Ion
    conf[poz] = 1;
    plani.push_back(poz);
    backtrack(poz+1, conf, plani, planj);
    plani.pop_back();

    // Pune în Vasile
    conf[poz] = 0;
    planj.push_back(poz);
    backtrack(poz+1, conf, plani, planj);
    planj.pop_back();
}

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

    bitset<NMAX> conf;
    vector<int> plani, planj;
    backtrack(1, conf, plani, planj);

    fout << fixed << setprecision(1) << dif << '\n';
    for(int i=1; i<=n; i++){
        fout << (fina[i] ? 'I' : 'V');
    }
    fout << '\n';

    return 0;
}