Cod sursa(job #3271188)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 25 ianuarie 2025 13:12:06
Problema Gradina Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.49 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 = {50000001, 50000001};
    int pos = -1;
    for(int i = 0; i < v.size(); i++) {
        if(v[i].x < p0.x || (v[i].x == p0.x && v[i].y < p0.y)) {
            p0 = v[i];
            pos = i;
        }
    }
    if(pos > 0)
        swap(v[0], v[pos]);
    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 = "";
            for(int i = 1; i <= st.size() + dr.size(); i++)
                ion += 'V';
            bool ok = 0; ///0 --> vasile, 1 --> ion
            for(int i = 0; i < st.size(); i++) {
                if(st[i].ind == 1) {
                    ok = 1;
                    break;
                }
            }
            ///FORMAM stringul
            if(ok) { ///e in st
                for(int i = 0; i < st.size(); i++)
                    ion[st[i].ind - 1] = 'I';
            }
            else {
                for(int i = 0; i < st.size(); i++)
                    ion[dr[i].ind - 1] = 'I';
            }
            if(diff < ans) {
                ans = diff;
                ch = ion;
            }
            else if(ans == diff) {
                for(int i = 0; i < ch.size(); i++) {
                    if(ch[i] < ion[i]) ///e ok, nu schimbam
                        return;
                    if(ch[i] > ion[i]) { ///schimbam
                        ch = ion;
                        return;
                    }
                }
            }
            //cout << "CODEFORCES " << diff << " " << ion << '\n';
        }
    }
}

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';
    }
    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 || i == p2)
                    continue;
                if(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();
            st.push_back(a[p1]), dr.push_back(a[p2]);
            check();

            st.clear(), dr.clear();
        }
    }
    cout << setprecision(1) << fixed << (ld)ans / 2.0;
    cout << '\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]
*/