Cod sursa(job #993422)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 3 septembrie 2013 19:36:37
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 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, s;
bitset <NMAX> in_stack;
char S[NMAX], R[NMAX];

inline long long modul (long long a) {

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

}

inline long long 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);

}

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]]) < 0 && head > 1)
            in_stack[_stack[head--]] = 1;
        in_stack[_stack[++head] = 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]]) < 0 && head > 1)
            --head;
        _stack[++head] = P[o];
    }
}

inline long long aria () {

    long long A = 0;
    _stack[++head] = _stack[1];
    for (o = 1; o < head; ++o)
        A += cross_product (V[0], V[_stack[o]], V[_stack[o + 1]]);
    return modul (A);

}

inline void make_solution () {

    for (o = 1; o <= l; ++o)
        S[V[ind[o]].p] = 'I';
    for (o = 1; 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;
    scanf ("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf ("%d%d", &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[i], V[j], V[k]) > 0 ? 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", (double) DIFF / 2.0, R);

}