Cod sursa(job #3248274)

Utilizator XTrim07Florea Andrei XTrim07 Data 11 octombrie 2024 13:28:59
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int MAX_SIZE = 120000;

int minim = 1e9;

int stk[MAX_SIZE + 1];
int sol[MAX_SIZE + 1];

struct date {
    double x, y;
    int parte;
    int ord;
    //int tip
} puncte[MAX_SIZE + 1], s1[MAX_SIZE + 1], s2[MAX_SIZE + 1];

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

double arie(date a, date b, date 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(date v[], int n) {
    for (int i = 2; i < n; ++i) {
        if (arie(v[1], v[n], v[i]) < 0) {
            v[i].parte = 1;
        } else {
            v[i].parte = 2;
        }
    }

    int k = 1;
    stk[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (v[i].parte == 1 || v[i].parte == 0) {
            while (k > 1 && arie(v[stk[k - 1]], v[stk[k]], v[i]) < 0) {
                --k;
            }
            ++k;
            stk[k] = i;
        }
    }
    int copy_k = k;
    stk[k] = n;
    for (int i = n - 1; i >= 1; --i) {
        if (v[i].parte == 2 || v[i].parte == 0) {
            while (k > copy_k && arie(v[stk[k - 1]], v[stk[k]], v[i]) < 0) {
                --k;
            }
            ++k;
            stk[k] = i;
        }
    }
    --k; //invata de ce
    double suma = 0;
    for (int i = 2; i < k; ++i) {
        suma += abs(arie(v[1], v[i], v[i + 1])) / 2.0;
    }
    return suma;
}

void diferenta(int n) {
    int cnt1 = 0;
    int cnt2 = 0;
    for (int i = 1; i <= n; i++) {
        if (puncte[i].parte == 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) == minim) {
         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].parte) { //in loc de tip pun parte
                break;
            }
            if (csol[i] == puncte[i].parte) {
                continue;
            }
            if (csol[i] < puncte[i].parte) {
                return;
            }
        }
        for (int i = 1; i <= n; ++i) {
            sol[i] = csol[i];
        }
    }
    if (abs(sum1 - sum2) < minim) {
        minim = abs(sum1 - sum2);
        for (int i = 1; i <= n; ++i) {
            sol[puncte[i].ord] = puncte[i].parte;
        }
    }
}

int main() {
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> puncte[i].x >> puncte[i].y;
        puncte[i].ord = i; //vezi de ce
    }
    sort(puncte + 1, puncte + n + 1, comp);
    for (int i = 1; i < n; ++i) {
        for (int j = 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].parte = 1; //inainte puncte[k].tip
                    } else {
                        puncte[k].parte = 2;
                    }
                }
                puncte[i].parte = 1;
                puncte[j].parte = 2;

                diferenta(n);

                puncte[i].parte = 2;
                puncte[j].parte = 1;

                diferenta(n);
            }
        }
    }
    fout << minim;
    for (int i = 1; i <= n; ++i) {
        if (sol[i] == sol[1]) {
            fout << 'I';
        } else {
            fout << 'V';
        }
    }
    return 0;
}