Cod sursa(job #67381)

Utilizator dominoMircea Pasoi domino Data 24 iunie 2007 15:04:28
Problema Gradina Scor Ascuns
Compilator cpp Status done
Runda Marime 2.67 kb
#include <stdio.h>
#include <algorithm>
#include <string>

using namespace std;

#define MAX_N 405
#define FIN "gradina.in"
#define FOUT "gradina.out"
#define x first.first
#define y first.second
#define idx second
#define mp make_pair
#define abs(x) ((x) < 0 ? -(x) : (x))

typedef pair<pair<int, int>, int> point;

int N, n1, n2, L[MAX_N], R[MAX_N], nl, nr;
point P[MAX_N], P1[MAX_N], P2[MAX_N];
char inL[MAX_N], inR[MAX_N];
pair<double, string> Res;

int sgn(point a, point b, point c)
{
    long long t = (long long) (b.x-a.x)*(c.y-a.y) - (long long) (c.x-a.x)*(b.y-a.y);
    return t < 0 ? -1 : t > 0 ? +1 : 0;
}

double convex_hull(point P[], int N)
{
    int i, n;
    double area = 0.0;

    if (N < 3) return -1.0;

    L[0] = R[0] = 0; nl = 2;
    L[1] = R[1] = 1; nr = 2;
    inL[0] = inL[1] = inR[0] = inR[1] = 1;
    for (i = 2; i < N; i++)
    {
        for (; nl > 1 && sgn(P[L[nl-1]], P[L[nl-2]], P[i]) < 0; nl--)
        {
            inL[n = L[nl-1]] = 0;
            if (!inR[n]) return -1.0;
        }
        for (; nr > 1 && sgn(P[R[nr-1]], P[R[nr-2]], P[i]) > 0; nr--)
        {
            inR[n = R[nr-1]] = 0;
            if (!inL[n]) return -1.0;
        }
        inL[L[nl++] = i] = inR[R[nr++] = i] = 1;
    }

    if (nl+nr != N+2) return -1.0;

    for (i = nr-2; i >= 0; i--) L[nl++] = R[i];
    for (i = 0; i+1 < nl; i++)
        area += (double) P[L[i]].x*P[L[i+1]].y - (double) P[L[i+1]].x*P[L[i]].y;
    return abs(area);
}

string rev(string s)
{
    int i;
    
    for (i = 0; i < s.size(); i++)
        s[i] = s[i] == 'I' ? 'V' : 'I';
    return s;
}

int main(void)
{
    int i, j, k;
    double a1, a2;
    string s;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);
    for (i = 0; i < N; i++)
    {
        scanf("%d %d", &P[i].x, &P[i].y);
        P[i].idx = i;
    }

    sort(P, P+N);

    Res = mp(1e13, "");
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
        {
            if (i == j) continue;
            s.resize(N);
            n1 = n2 = 0;
            for (k = 0; k < N; k++)
            {
                if (k == j || (k != i && sgn(P[min(i, j)], P[max(i, j)], P[k]) < 0))
                    P1[n1++] = P[k], s[P[k].idx] = 'I';
                else
                    P2[n2++] = P[k], s[P[k].idx] = 'V';
            }
            s = min(s, rev(s));

            if ((a1 = convex_hull(P1, n1)) < 0.0) continue;
            if ((a2 = convex_hull(P2, n2)) < 0.0) continue;

            Res = min(Res, mp(abs(a1-a2), s));
        }

    printf("%.1f\n%s\n", Res.first*0.5, Res.second.c_str());

    return 0;
}