Cod sursa(job #993329)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 3 septembrie 2013 17:23:19
Problema Gradina Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.97 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>
#define x first.first
#define y first.second
#define p second
using namespace std;

typedef pair <pair <int, int>, int> point;
const int NMAX = 253;

point V[NMAX];
int ind[NMAX], _ind[NMAX], _stack[NMAX], l, _l, head, o, _o, s;
bitset <NMAX> in_stack;
char S[NMAX];

inline long long modul (long long a) {

    if (a < 0)
        return -a;
    return a;

}

inline bool cross_product (const point &a, const point &b, const point &c) {

    return (b.x - a.x) * 1LL * (c.y - a.y) > (b.y - a.y) * 1LL * (c.x - a.x);

}

inline long long _cross_product (const point &a, const point &b) {

    return a.x * 1LL * b.y - a.y * 1LL * b.x;

}

void convex_hull (const int &N, int *P) {

    head = 2;
    in_stack.set ();
    _stack[1] = P[1];
    _stack[2] = P[2];
    in_stack[P[1]] = in_stack [P[2]] = 0;
    for (o = 3; o <= N; ++o) {
        while (!cross_product (V[P[o]], V[_stack[head - 1]], V[_stack[head]]) && head > 1)
            in_stack[_stack[head]] = 1, --head;
        _stack[++head] = P[o];
        in_stack[P[o]] = 0;
    }
    for (o = N - 1; o >= 1; --o) {
        if (!in_stack[P[o]])
            continue;
        while (!cross_product (V[P[o]], V[_stack[head - 1]], V[_stack[head]]) && head > 1)
            --head;
        _stack[++head] = P[o];
    }
}

inline long long aria () {

    long long A = 0;
    int i;
    _stack[0] = _stack[head];
    for (i = 1; i <= head; ++i)
        A += _cross_product (V[_stack[i - 1]], V[_stack[i]]);
    return A;

}

inline void make_solution () {

    o = 1;
    _o = 1;
    s = 2;
    bool k;
    if (ind[1] == 1)
        S[V[ind[1]].p] = 'I', k = 0, ++o;
    else
        S[V[_ind[1]].p] = 'I', k = 1, ++_o;
    while (o <= l && _o <= _l)
        if (ind[o] == s)
            S[V[ind[o]].p] = (k ? 'V' : 'I'), ++o, ++s;
        else
            S[V[_ind[_o]].p] = (k ? 'I' : 'V'), ++_o, ++s;
    if (o <= l)
        if (k)
            for (; o <= l; ++o)
                S[V[ind[o]].p] = 'V';
        else
            for (; o <= l; ++o)
                S[V[ind[o]].p] = 'I';
    else
        if (k)
            for (; _o <= _l; ++_o)
                S[V[ind[_o]].p] = 'I';
        else
            for (; _o <= _l; ++_o)
                S[V[ind[_o]].p] = 'V';

}

int main () {

    freopen ("gradina.in", "r", stdin);
    freopen ("gradina.out", "w", stdout);
    long long A, _A, DIFF = 2e18;
    int N, i, j, k;
    char *R = new char[NMAX];
    cin >> N;
    for (i = 1; i <= N; ++i)
        cin >> V[i].x >> V[i].y,
        V[i].p = i;
    sort (V + 1, V + N + 1);
    for (i = 1; i <= N; ++i)
        for (j = 1; j <= N; ++j)
            if (i != j) {
                l = _l = 0;
                for (k = 1; k <= N; ++k)
                    if (k == i)
                        ind[++l] = k;
                    else
                        if (k == j)
                            _ind[++_l] = k;
                        else
                            cross_product (V[k], V[i], V[j]) ? ind[++l] = k : _ind[++_l] = k;
                if (l < 3 || _l < 3)
                    continue;
                convex_hull (l, ind);
                if (head != l)
                    continue;
                A = aria ();
                convex_hull (_l, _ind);
                if (head != _l)
                    continue;
                _A = aria ();
                if (modul (A - _A) < DIFF) {
                    DIFF = modul (A - _A);
                    make_solution ();
                    strcpy (R, S + 1);
                }
               else
                    if (modul (A - _A) == DIFF) {
                        make_solution ();
                        if (strcmp (S + 1, R) < 0)
                            strcpy (R, S + 1);
                    }

            }
    printf ("%.1lf\n%s", (float) DIFF / 2, R);

}