Cod sursa(job #3270258)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 22 ianuarie 2025 18:48:42
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <stack>
#include <climits>
#include <iomanip>
#include <algorithm>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;
using db = double;

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

struct punct{
    db x, y, idx;

    bool operator == (punct b){
        return (b.x == x && b.y == y);
    }
};

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

punct start;
bool cmp(punct a, punct b){
    if(a == start) return true;
    if(b == start) return false;
    return (det( start, a, b ) > 0);
}

bool e_convex(vector< punct > & v){
    for(int i = 2; i < v.size(); i++){
        if(det( v[i - 2], v[i - 1], v[i] ) < 0) return 0;
    }
    return 1;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; in >> n;
    punct v[n];

    db mini = 50000001;
    string sol; 
    for(int i = 0; i < n; i++) sol.push_back('V');
    start.x = start.y = 0;
    for(int i = 0; i < n; i++){
        in >> v[i].x >> v[i].y;
        v[i].idx = i;
    }

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

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

            vector< punct > st, dr;
            for(int k = 0; k < n; k++){
                if( det(v[i], v[j], v[k]) > 0 ) st.push_back(v[k]);
                else dr.push_back(v[k]);
            }

            bool convex_1 = e_convex(st), convex_2 = e_convex(dr);

            if(!convex_1 || !convex_2) continue;
            // cout << "Stabilim I ( " << v[i].x << " , " << v[i].y << " ) si J ( " << v[j].x << " , " << v[j].y << " )\n";
            // cout << "  -- > st : ";
            // for(int k = 0; k < st.size(); k++) cout << "( " << st[k].x << " , " << st[k].y << " ) ";
            // cout << '\n';

            // cout << "  -- > dr : ";
            // for(int k = 0; k < dr.size(); k++) cout << "( " << dr[k].x << " , " << dr[k].y << " ) ";
            // cout << '\n';
            
            db A1 = 0, A2 = 0;
            for(int k = 0; k + 1 < st.size(); k++){
                A1 += st[k].x * st[k + 1].y - st[k + 1].x * st[k].y;
            }
            A1 += st.back().x * st[0].y - st[0].x * st.back().y;


            for(int k = 0; k + 1 < dr.size(); k++){
                A2 += dr[k].x * dr[k + 1].y - dr[k + 1].x * dr[k].y;
            }
            A2 += dr.back().x * dr[0].y - dr[0].x * dr.back().y;

            A1 /= 2; A2 /= 2;

            // cout << "  -- > A1 = " << A1 << " A2 = " << A2 << '\n';

            if(abs(A1 - A2) < mini) mini = abs(A1 - A2);
            if(mini == abs(A1 - A2)){
                string s;
                s.resize(n);
                for(int k = 0; k < st.size(); k++) s[ st[k].idx ] = 'I'; 
                for(int k = 0; k < dr.size(); k++) s[ dr[k].idx ] = 'V';

                if(s[0] == 'V'){
                    for(int k = 0; k < n; k++){
                        if(s[i] == 'I') s[i] = 'V';
                        else s[i] = 'I';
                    }
                }

                sol = min(sol, s);
            }
        }
    }

    out << fixed << setprecision(1) << mini << '\n';
    out << sol << '\n';

    return 0;
}