Cod sursa(job #3244055)

Utilizator StefanStratonStefan StefanStraton Data 23 septembrie 2024 10:40:24
Problema Gradina Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.04 kb
#include <algorithm>
#include <cstring>
#include <fstream>
#define NMax 256
#define INF 4000000000000000000LL

using namespace std;
int n;
struct point_data_type{
    int x, y;
    int ind;
    point_data_type () {}
    // am 2 tipuri de puncte
    point_data_type (const int _x, const int _y){
        x = _x; y = _y;
    }
    point_data_type (const int _x, const int _y, const int _ind){
        x = _x; y = _y; ind = _ind;
    }
    bool operator <(const point_data_type &other) const{
        if (x == other.x) return y < other.y;
        return x < other.x;
    }
};

inline long long determinant(const point_data_type &A, const point_data_type &B, const point_data_type &C)
{
    return 1LL*(A.x-C.x)*(B.y-C.y) - 1LL*(B.x-C.x)*(A.y-C.y); // o alta formula pentru determinant
}
point_data_type a[NMax], v_ion[NMax], v_vasile[NMax];
int n_ion, n_vasile;

inline long long infasuratoare_convexa(const point_data_type *_v, const int v_size)
{
    point_data_type v[NMax], st[NMax], rezultat[NMax];
    int v_size_aux = 0, nconvex = 0;
    for (int i = 1; i<=n; ++i)
        if (_v[i].x != -50000001) v[++v_size_aux] = _v[i];
    int vf = 0;

    st[++vf] = v[1], st[++vf] = v[2];
    for (int i = 3; i<=v_size; ++i)
    {
        while (vf >= 2 && determinant(st[vf-1], st[vf], v[i]) < 0)
            --vf;
        st[++vf] = v[i];
    }
    for (int i = 1; i<vf; ++i) rezultat[++nconvex] = st[i];

    for (int i = 1, j = v_size; i<=j; ++i, --j) swap(v[i], v[j]);

    vf = 0;
    st[++vf] = v[1], st[++vf] = v[2];
    for (int i = 3; i<=v_size; ++i)
    {
        while (vf >= 2 && determinant(st[vf-1], st[vf], v[i]) < 0)
            --vf;
        st[++vf] = v[i];
    }
    for (int i = 1; i<vf; ++i) rezultat[++nconvex] = st[i];

    if (nconvex == v_size)
    {
        long long ret = 0;
        int i, j, k;
        for (i = 1, j = 2, k = 3; k <= nconvex; ++j, ++k)
            ret += abs(determinant(rezultat[i], rezultat[j], rezultat[k]));
        return ret;
    }
    return -1LL;
}

int main()
{
    ifstream f ("gradina.in"); ofstream g ("gradina.out");
    f >> n;
    for(int i = 1; i <= n; ++i){
        int x, y;
        f >> x >> y;
        a[i] = point_data_type(x, y, i);
    }
    sort(a + 1, a + n + 1);
    long long  dif_min = INF;
    char solutia_finala[NMax], solutia_curenta[NMax];
    memset(solutia_finala, 0, sizeof(solutia_finala));
    memset(solutia_curenta, 0, sizeof(solutia_curenta));
    int i, j ,k;
    for (i = 1; i<=n; ++i){
        for (j = 1; j<=n; ++j){
            if (i == j) continue;
            n_ion = n_vasile = 0;
            for (int k = 1; k <= n; ++k)
                v_ion[k] = v_vasile[k] = point_data_type(-50000001, -50000001);
            v_ion[j] = a[j], v_vasile[i] = a[i];
            ++n_ion, ++n_vasile;
            solutia_curenta[a[j].ind] = 'I', solutia_curenta[a[i].ind] = 'V';
            for (k = 1; k <= n; ++k)
                if (k!=i && k!=j)
                    if (determinant(a[i], a[j], a[k]) < 0)
                        ++n_ion, v_ion[k] = a[k], solutia_curenta[a[k].ind] = 'I';
                    else
                        ++n_vasile, v_vasile[k] = a[k], solutia_curenta[a[k].ind] = 'V';
            if (n_ion >= 3 && n_vasile >= 3)
            {
                long long ai, av;
                ai = infasuratoare_convexa(v_ion, n_ion); av = infasuratoare_convexa(v_vasile, n_vasile);
                if (ai == -1 || av == -1) continue;

                long long dif_curenta = abs(ai - av);
                if ( dif_curenta < dif_min )
                {
                    dif_min = dif_curenta;
                    for (int k = 1; k<=n; ++k)
                        solutia_finala[k] = solutia_curenta[k];
                }
                else if (dif_curenta == dif_min && strcmp(solutia_finala + 1, solutia_curenta + 1) > 0)
                    for (int k = 1; k<=n; ++k) solutia_finala[k] = solutia_curenta[k];
            }
        }
    }
    g <<  1.0 * dif_min / 2 << '\n' <<  solutia_finala+1;
    return 0;
}