Cod sursa(job #993345)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 3 septembrie 2013 17:48:14
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 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];

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;
    _stack[0] = _stack[head];
    for (o = 1; o <= head; ++o)
        A += _cross_product (V[_stack[o - 1]], V[_stack[o]]);
    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];
    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 ("%.1f\n%s", (float) DIFF / 2.0, R);

}