Cod sursa(job #1148919)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 21 martie 2014 12:10:30
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.83 kb
#include <algorithm>
#include <cstring>
#include <fstream>
#define NMax 256
#define INF 4000000000000000000LL

using namespace std;

int n;
struct punct
{
    int x, y;
    int ind;
    punct () {}
    punct (const int _x, const int _y)
    {
        x = _x;
        y = _y;
    }
    punct (const int _x, const int _y, const int _ind)
    {
        x = _x;
        y = _y;
        ind = _ind;
    }
    bool operator <(const punct &other) const
    {
        if (x == other.x)
            return y < other.y;
        return x < other.x;
    }
};
punct a[NMax], vi[NMax], vv[NMax], ca[NMax];
int ni, nv;

void Read()
{
    ifstream f ("gradina.in");
    f>>n;
    for (int i = 1; i<=n; ++i)
    {
        int x, y;
        f>>x>>y;
        ca[i] = a[i] = punct(x, y, i);
    }
    f.close();
}

inline long long Det(const punct &A, const punct &B, const punct &C)
{
    return 1LL*(A.x-C.x)*(B.y-C.y) - 1LL*(B.x-C.x)*(A.y-C.y);
}

inline long long ConvexHull(const punct *_v, const int sz)
{
    punct v[NMax], st[NMax], convex[NMax];
    int sz_aux = 0, nconvex = 0;
    for (int i = 1; i<=n; ++i)
        if (_v[i].x != -50000001)
            v[++sz_aux] = _v[i];
    int vf = 0;

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

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

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

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

void Solve()
{
    sort (a+1, a+n+1);
    long long  diffans = INF;
    char Sir[NMax], localSir[NMax];
    memset(Sir, 0, sizeof(Sir));
    memset(localSir, 0, sizeof(localSir));
    int i, j ,k;
    for (i = 1; i<=n; ++i)
    {
        for (j = 1; j<=n; ++j)
        {
            if (i == j)
                continue;
            ni = nv = 0;
            for (int index = 1; index <= n; ++index)
                vi[index] = vv[index] = punct(-50000001, -50000001);
            vi[j] = a[j], vv[i] = a[i];
            ++ni, ++nv;
            localSir[a[j].ind] = 'I', localSir[a[i].ind] = 'V';
            for (k = 1; k <= n; ++k)
                if (k!=i && k!=j)
                    if (Det(a[i], a[j], a[k]) < 0)
                        ++ni, vi[k] = a[k], localSir[a[k].ind] = 'I';
                    else
                        ++nv, vv[k] = a[k], localSir[a[k].ind] = 'V';
            if (ni >= 3 && nv >= 3)
            {
                long long ai, av;
                ai = ConvexHull(vi, ni);
                av = ConvexHull(vv, nv);
                if (ai == -1 || av == -1)
                    continue;
                long long diff = abs(ai - av);
                if ( diff < diffans )
                {
                    diffans = diff;
                    for (int index = 1; index<=n; ++index)
                        Sir[index] = localSir[index];
                }
                else if (diff == diffans && strcmp(Sir + 1, localSir + 1) > 0)
                    for (int index = 1; index<=n; ++index)
                        Sir[index] = localSir[index];
            }
        }
    }
    FILE *g = fopen("gradina.out", "w");
    fprintf(g, "%.1lf\n%s\n", 1.0*diffans / 2, Sir+1);
    fclose(g);
}

int main()
{
    Read();
    Solve();
    return 0;
}