Cod sursa(job #3270299)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 22 ianuarie 2025 19:53:18
Problema Gradina Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.28 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 = float;

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){
    a.x -= c.x;
    a.y -= c.y;
    b.x -= c.x;
    b.x -= c.y;
    return ( a.x * b.y - b.x * c.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;
}

bool min(string & a, string & b){
    for(int i = 0; i < a.size(); i++){
        if(a[i] > b[i]) return 1;
        if(a[i] < b[i]) return 0;
    }
    return 0;
}

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

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

    db mini = 500000001;
    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 = i + 1; 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]);
            }

            if(st.size() < 3 || dr.size() < 3) continue;

            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) / (db)2;
            }
            A1 += (st.back().x * st[0].y - st[0].x * st.back().y) / (db)2;


            for(int k = 0; k + 1 < dr.size(); k++){
                A2 += (dr[k].x * dr[k + 1].y - dr[k + 1].x * dr[k].y) / (db)2;
            }
            A2 += (dr.back().x * dr[0].y - dr[0].x * dr.back().y) / (db)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(min(s, sol) == 0) sol = s;
            }
        }
    }

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

    return 0;
}