Cod sursa(job #3271218)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 25 ianuarie 2025 14:08:08
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.89 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>

using namespace std;
const int NMAX = 252;
using ld = long double;
using ll = long long;

ifstream cin("gradina.in");
ofstream cout("gradina.out");

struct puncte {
    ll x, y;
    int ind;
}a[NMAX];
vector <puncte> st, dr;

ll determ(puncte a, puncte b, puncte c) {
    return a.x * b.y + b.x * c.y + c.x * a.y -
           a.y * b.x - b.y * c.x - c.y * a.x;
}
ll ans = 1e18;
string ch;

puncte p0;
bool cmp(puncte a, puncte b) { ///panta inmultita
    return (b.x - p0.x) * (a.y - p0.y) < (a.x - p0.x) * (b.y - p0.y);
}

bool infasuratoare(vector <puncte> &v) {
    p0 = v[0]; ///asa ar trebui, ca deja sunt sortate

    sort(v.begin() + 1, v.end(), cmp);
    for(int i = 2; i < v.size(); i++) {
        if(determ(v[i - 2], v[i - 1], v[i]) < 0)
            return false;
    }
    if(determ(v[v.size() - 2], v[v.size() - 1], v[0]) < 0 ||
       determ(v[v.size() - 1], v[0], v[1]) < 0)
        return false;
    return true;
}

ll arie(vector <puncte> &v) { ///LA FINAL /2
    ll sum = 0;
    for(int i = 0; i + 1 < v.size(); i++)
        sum += (v[i].x * v[i + 1].y - v[i + 1].x * v[i].y);
    sum += (v[v.size() - 1].x * v[0].y - v[0].x * v[v.size() - 1].y);
    return sum;
}

void print() {
    cout << "yoo\n";
    for(int i = 0; i < st.size(); i++)
        cout << st[i].ind << " ";
    cout << '\n';
    for(int i = 0; i < dr.size(); i++)
        cout << dr[i].ind << " ";
    cout << '\n';
}

void check() { ///cu st si dr
    if(st.size() < 3 || dr.size() < 3) ///n-ai csf
        return;
    if(infasuratoare(st) && infasuratoare(dr)) {
        //print();
        ll a1 = arie(st), a2 = arie(dr);
        ll diff = abs(a1 - a2);
        if(diff <= ans) {
            string ion = "";
            ion.resize(st.size() + dr.size());
            for(int i = 0; i < st.size(); i++)
                ion[st[i].ind - 1] = 'I';
            for(int i = 0; i < dr.size(); i++)
                ion[dr[i].ind - 1] = 'V';
            if(ion[0] == 'V') {
                for(int i = 0; i < ion.size(); i++) {
                    if(ion[i] == 'V')
                        ion[i] = 'I';
                    else
                        ion[i] = 'V';
                }
            }
            if(diff < ans || (ans == diff && ion < ch)) {
                //cout << diff << " " << ion << '\n';
                ans = diff;
                ch = ion;
            }
            //cout << "CODEFORCES " << diff << " " << ion << '\n';
        }
    }
}
bool cmpdir(puncte a, puncte b) {
    if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
        a[i].ind = i;
        ch += 'V';
    }
    sort(a + 1, a + n + 1, cmpdir);
    for(int p1 = 1; p1 <= n; p1++) {
        for(int p2 = 1; p2 <= n; p2++) {
            if(p1 == p2)
                continue;
            for(int i = 1; i <= n; i++) {
                if(i == p1 || determ(a[p1], a[p2], a[i]) < 0)
                    st.push_back(a[i]);
                else
                    dr.push_back(a[i]);
            }
            //cout << "deci " << p1 << " " << p2 << '\n';
            //cout << "test run ";
            //print();
            check();
            st.clear(), dr.clear();
        }
    }
    cout << setprecision(1) << fixed << (ld)ans / 2.0 << '\n' << ch;
    return 0;
}
/*
- iei cate 2 puncte si le imparti pe celelalte in functie de
  partea dreptei pe care sunt
- pt ambele 2 multimi de planuri, faci infasuratoare, DAR
  iei cele 2 puncte ce formeaza dreapta in fiecare in parte,
  ca sa incerci (si unul cu unul, si impreuna)
- dc MERG ambele infasuratori si includ TOTI tarusii, compari aria
- cum stii care-i Ion? In functie de care parte include v[1]
*/