Cod sursa(job #1010196)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 14 octombrie 2013 14:57:01
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 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, 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) {

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

}

inline void make_solution () {

    int i;
    for (i = 1; i <= l; ++i)
        S[V[ind[i]].p] = 'I';
    for (i = 1; i <= _l; ++i)
        S[V[_ind[i]].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, m;
    char R[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 = 0;
                _stack[++head] = _stack[1];
                for (m = 1; m < head; ++m)
                    A += 1LL * V[_stack[m]].x * V[_stack[m + 1]].y - 1LL * V[_stack[m]].y * V[_stack[m + 1]].x;
                A = modul (A);
                convex_hull (_l, _ind);
                if (head != _l)
                    continue;
                _A = 0;
                _stack[++head] = _stack[1];
                for (m = 1; m < head; ++m)
                    _A += 1LL * V[_stack[m]].x * V[_stack[m + 1]].y - 1LL * V[_stack[m]].y * V[_stack[m + 1]].x;
                _A = modul (_A);
                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", (double) DIFF / 2.0);
    printf ("\n%s", R);

}