Cod sursa(job #993624)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 4 septembrie 2013 10:53:20
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 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, p;
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 a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0 ;

}

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

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

inline long long aria () {

    long long A = 0;
    _stack[++head] = _stack[1];
    for (o = 1; o < head; ++o)
        A += 1LL * V[_stack[o]].x * V[_stack[o + 1]].y - 1LL * V[_stack[o]].y * V[_stack[o + 1]].x;
    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;
    char *R = new char[NMAX];
    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]) ? 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);

}