Cod sursa(job #67352)

Utilizator filipbFilip Cristian Buruiana filipb Data 24 iunie 2007 13:52:36
Problema Gradina Scor Ascuns
Compilator cpp Status done
Runda Marime 3.72 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define CLEAR(x) memset(x, 0, sizeof(x))
#define ll long long
#define INF 900000000
#define NMax 405
typedef struct { int x, y, ord; } punct;
typedef punct point_set[NMax];

int N;
point_set v, A, B;

ll bst = (ll)INF * INF;
char SOL[NMax], Res[NMax];

int cmp(const punct& a, const punct& b)
{ return (a.y < b.y) || (a.y == b.y && a.x < b.x); }

int semn(punct A, punct B, punct C)
{
    ll a = A.y-B.y, b = B.x-A.x, c = (ll)A.x * B.y - (ll)B.x * A.y;
    ll E = a * C.x + b * C.y + c;

    if (E < 0) return -1;
    if (E > 0) return +1;
    return 0;
}

ll area(punct A, punct B, punct C)
{
   ll E = ((ll)(B.x - A.x)) * ((ll)(C.y - A.y)) -
            ((ll)(C.x - A.x)) * ((ll)(B.y - A.y));

   if (E < 0) E = -E;

   return E;
}

int st[NMax], uz[NMax];

ll ConvexHull(point_set X, int nr)
// returneaza 0 daca X nu e poligon convex sau dublul ariei lui daca este
{
    int i, k, pas = +1; ll S = 0;

    if (nr < 3) return 0;

    CLEAR(st); CLEAR(uz);
    st[1] = 1; st[2] = 2; uz[2] = 1; k = 2; i = 2;
    
    while (!uz[1])
    {
        while (uz[i])
        {
           i += pas;
           if (i == nr)
              pas = -1;
        }

        while (k >= 2 && semn(X[st[k-1]], X[st[k]], X[i]) < 0)
              uz[st[k--]] = 0;
        st[++k] = i; uz[i] = 1;
    }

    st[k--] = 0;
    if (nr == k)
    {
        for (i = 1, S = 0; i <= nr-2; i++)
            S += area(X[st[1]], X[st[i+1]], X[st[i+2]]);
        return S;
    }

    return 0;
}

int main(void)
{
    int i, j, k, E; ll S1, S2, diff; int p1, p2;
    
    freopen("gradina.in", "r", stdin);
    freopen("gradina.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d %d", &v[i].x, &v[i].y);
        v[i].ord = i;
    }

    sort(v+1, v+N+1, cmp);

    for (i = 0; i <= N; i++) SOL[i] = 'Z';

    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
        {
            if (i == j) continue;

            for (k = 1, p1 = 0, p2 = 0; k <= N; k++)
                if (k != i && k != j)
                {
                   E = semn(v[i], v[j], v[k]);
                   
                   if (E > 0)
                        A[++p1] = v[k];
                   else if (E < 0)
                        B[++p2] = v[k];
                }
                else if (k == i)
                   A[++p1] = v[i];
                else if (k == j)
                   B[++p2] = v[j];


            if (i == 4 && j == 5)
                k = 0;


            S1 = ConvexHull(A, p1);
            if (!S1) continue;
            S2 = ConvexHull(B, p2);
            if (!S2) continue;


            diff = S1-S2; if (diff < 0) diff = -diff;
            if (diff <= bst)
            {
                bst = diff;
                for (k = 0; k <= N; k++) Res[k] = ' ';
                for (k = 1; k <= p1; k++)
                    Res[A[k].ord] = 'I';
                for (k = 1; k <= p2; k++)
                    Res[B[k].ord] = 'V';

                if (Res[1] == 'V')
                   for (k = 1; k <= N; k++)
                        if (Res[k] == 'I') Res[k] = 'V';
                        else Res[k] = 'I';

                for (k = 1, E = 0; k <= N; k++)
                    if (SOL[k] > Res[k])
                    { E = 1; break; }

                if (E)
                   for (k = 1; k <= N; k++)
                        SOL[k] = Res[k];
                        
            }
            
        }

    printf("%.1lf\n", ((double)bst) * 0.5);
    for (i = 1; i <= N; i++)
        printf("%c", SOL[i]);
    printf("\n");
    

    return 0;
}