Cod sursa(job #3246052)

Utilizator MariosulmarioMario Badea Mariosulmario Data 1 octombrie 2024 17:55:34
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

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

struct punct{
    int x, y, tip, ord;
}puncte[255], s1[255], s2[255];

int sol[255];
double minn = 1000000000;

bool cmp(punct a, punct b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

double arie(punct A, punct B, punct 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 infasuratoare_convexa(punct v[], int n) {
    int t[255], st[255];
    for (int i = 2; i < n; i++) {
        if (arie(v[1], v[n], v[i]) < 0)
            t[i] = 1;
        else
            t[i] = 2;
    }
    t[1] = t[n] = 0;
    int k = 1;
    st[1] = 1;
    for (int i = 2; i <= n; i++)
        if (t[i] == 1 || t[i] == 0) {
            while (k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
                return -1;
            k++;
            st[k] = i;
        }
    int ck = k;
    for (int i = n - 1; i >= 1; i--)
        if (t[i] == 2 || t[i] == 0) {
            while (k > ck && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
                return -1;
            k++;
            st[k] = i;
        }
    k--;
    double s = 0;
    for (int i = 2; i < k; i++)
        s += abs(arie(v[1], v[st[i]], v[st[i + 1]])) / 2.0;
    return s;
}

void diferenta(int n) {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++)
        if (puncte[i].tip == 1)
            s1[++cnt1] = puncte[i];
        else
            s2[++cnt2] = puncte[i];

    if (cnt1 < 3 || cnt2 < 3)
        return;
    double sum1 = infasuratoare_convexa(s1, cnt1);
    double sum2 = infasuratoare_convexa(s2, cnt2);
    if (sum1 < 0 || sum2 < 0)
        return;
    if(abs(sum1 - sum2) == minn) {
        int csol[n + 1];
        for (int i = 1; i <= n; i++)
            csol[i] = sol[i];
        for (int i = 1; i <= n; i++) {
            if (csol[i] > puncte[i].tip)
                break;
            if (csol[i] == puncte[i].tip)
                continue;
            if (csol[i] < puncte[i].tip)
                return;
        }
        for (int i = 1; i <= n; i++)
            sol[i] = csol[i];
    }
    if (abs(sum1 - sum2) < minn) {
        minn = abs(sum1 - sum2);
        for (int i = 1; i <= n; i++)
            sol[puncte[i].ord] = puncte[i].tip;
    }
}

int main()
{
    int n;
    in >> n;
    for (int i = 1;i <= n; i++) {
        in >> puncte[i].x >>puncte[i].y;
        puncte[i].ord = i;
    }
    sort(puncte + 1, puncte + n + 1, cmp);
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) {
            for (int k = 1; k <= n; k++)
                if (k != i && k != j) {
                    if (arie(puncte[i], puncte[j], puncte[k]) < 0)
                        puncte[k].tip = 1;
                    else
                        puncte[k].tip = 2;
                }
            puncte[i].tip = 1;
            puncte[j].tip = 2;
            diferenta(n);
            puncte[i].tip = 2;
            puncte[j].tip = 1;
            diferenta(n);
        }
    out << fixed << setprecision(1) << minn << "\n";
    for (int i = 1; i <= n; i++)
        if (sol[i] == sol[1])
            out << 'I';
        else
            out << 'V';
}