Cod sursa(job #3244086)

Utilizator StefanStratonStefan StefanStraton Data 23 septembrie 2024 15:51:44
Problema Gradina Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f ("gradina.in"); ofstream g ("gradina.out");

struct punct { int x, y; };
punct tarusi_Ion[252], tarusi_Vasile[252], a[252];

int stiva[252];
char sol_curenta[252];
double dif_min;
int n, aux;
int vfIon, vfVasile;
char sol_finala[252];
bool viz[252];


bool cmp (punct a, punct b){
    if (a.x > b.x) return false;
    if (a.x == b.x && a.y > b.y) return false;
    return true;
}

int det (punct a, punct b, punct c){
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

double arie_infasuratoare_convexa (punct p[], int m){
    double sol = 0;
    for (int i = 1; i <= m; i++)
        viz[i] = false;

    stiva[1] = 1; stiva[2] = 2;
    viz[2] = true;
    int vf = 2, poz = 2, pas = 1;

    while (viz[1] == false){ // pana ajung din nou la primul punct
        while (viz[poz] == true){
            poz += pas;
            if (poz == m) pas = -1;
        }

        while (vf >= 2 && det(p[stiva[vf - 1]], p[stiva[vf]], p[poz]) < 0){
            viz[stiva[vf]] = false;
            vf--;
        }
        vf++;
        stiva[vf] = poz;
        viz[poz] = true;
    }
    for (int i = 1; i < vf; i++) sol = sol + det(p[0], p[stiva[i]], p[stiva[i+1]]);

    sol = sol / 2;
    if (vf != m + 1) aux = 0;
    return sol;
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++) f >> a[i].x >> a[i].y;

    dif_min = 1000000000;

    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            vfIon = 0;
            vfVasile = 0;
            for (int k = 1; k <= n; k++){
                if (k == i || k == j || det(a[k], a[i], a[j]) < 0){
                    sol_curenta[k] = 'I';
                    vfIon++;
                    tarusi_Ion[vfIon] = a[k];
                }
                else{
                    sol_curenta[k] = 'V';
                    vfVasile++;
                    tarusi_Vasile[vfVasile] = a[k];
                }
            }
            if (vfIon < 3 || vfVasile < 3) continue;

            sort(tarusi_Ion + 1, tarusi_Ion + vfIon + 1, cmp);
            sort(tarusi_Vasile + 1, tarusi_Vasile + vfVasile + 1, cmp);

            aux = 1;
            double dif = abs(arie_infasuratoare_convexa(tarusi_Ion, vfIon) - arie_infasuratoare_convexa(tarusi_Vasile, vfVasile));

            if (aux == 0) continue;

            if (dif < dif_min){
                dif_min = dif;
                for (int k = 1; k <= n; k++) sol_finala[k] = sol_curenta[k];
            }
        }
    }

    g << setprecision(1) << fixed << dif_min << '\n';
    for (int i = 1; i <= n; i++) g << sol_finala[i];

    return 0;
}