Cod sursa(job #3247482)

Utilizator deerMohanu Dominic deer Data 7 octombrie 2024 22:41:56
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

using namespace std;
ifstream fin ("gradina.in");
ofstream fout ("gradina.out");
struct ura {
    int x, y, idx;
};

int arie(ura a, ura b, ura c) {
    return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}

double arie_poly(const vector<ura>& v) {
    int n = sz(v);
    double arie = 0;
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        arie += v[i].x * v[j].y - v[i].y * v[j].x;
    }
    return abs(arie) / 2.0;
}

bool convex_hull(vector<ura>& v) {
    if (sz(v) < 3) return false;
    vector<ura> stk;
    stk.push_back(v[0]);
    for (int i = 1; i < sz(v); ++i) {
        while (stk.size() > 1 && arie(stk[stk.size() - 2], stk.back(), v[i]) < 0)
            stk.pop_back();
        stk.push_back(v[i]);
    }
    v = stk;
    return sz(stk) == sz(v);
}

void solve_testcase() {
    int n;
    fin >> n;
    vector<ura> a(n);

    for (int i = 0; i < n; ++i) {
        fin >> a[i].x >> a[i].y;
        a[i].idx = i;
    }

    sort(all(a), [](const ura &a, const ura &b) {
        return make_pair(a.x, a.y) < make_pair(b.x, b.y);
    });

    double ans = 1e9;
    string best(n, 'I');

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            vector<ura> u, v;
            string cur(n, 'I');

            for (int k = 0; k < n; ++k) {
                if (k == i || k == j) continue;
                if (arie(a[i], a[j], a[k]) < 0) {
                    v.push_back(a[k]);
                    cur[a[k].idx] = 'V';
                } else {
                    u.push_back(a[k]);
                }
            }
            u.push_back(a[i]);
            v.push_back(a[j]);

            if (convex_hull(u) && convex_hull(v)) {
                double dif = abs(arie_poly(u) - arie_poly(v));
                if (cur[0] == 'V') {
                    for (auto &it : cur)
                        it = (it == 'V' ? 'I' : 'V');
                }
                if (dif < ans || (dif == ans && cur < best)) {
                    ans = dif;
                    best = cur;
                }
            }
        }
    }

    fout << fixed << setprecision(1) << ans << endl;
    fout << best << endl;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    // fin >> t;
    while (t--)
          solve_testcase();
    return 0;
}