Cod sursa(job #2310412)

Utilizator akaprosAna Kapros akapros Data 31 decembrie 2018 15:23:40
Problema Gradina Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <bits/stdc++.h>
#define maxN 252
#define ll long long
#define inf 2LL * (0x3fffffff) * (0x3fffffff)
using namespace std;

FILE *fin = freopen("gradina.in", "r", stdin);
FILE *fout = freopen("gradina.out", "w", stdout);

int n;
struct Point
{
    int x, y, id;
    bool operator < (const Point &ot) const
    {
        if (x == ot.x)
            return y < ot.y;
        return x < ot.x;
    }
} V[maxN];
int st[2][maxN];
bool vis[2][maxN];

ll ans;
char sol[2][maxN];

ll CrossProduct(Point O, Point A, Point B)
{
    return 1LL * (A.x - O.x) * (B.y - O.y) - 1LL * (B.x - O.x) * (A.y - O.y);
}

ll Det(Point A, Point B)
{
    return 1LL * A.x * B.y - 1LL * A.y * B.x;
}
int f(Point a, Point b, Point P)
{
    if (P.x == a.x && P.y == a.y) return 0;
    if (P.x == b.x && P.y == b.y) return 1;
    return (1LL * (a.y - b.y) * P.x + 1LL * (b.x - a.x) * P.y + 1LL * a.x * b.y - 1LL * a.y * b.x) > 0;
}
ll HullDif(int a, int b)
{
    memset(vis, 0, sizeof(vis));
    int head[2] = {0, 0};
    for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p)))
    {
        int t = f(V[a], V[b], V[i]);
        if (t) sol[0][V[i].id] = 'V';
        else
            sol[0][V[i].id] = 'I';
        if (vis[t][i]) continue;
        while (head[t] >= 2 && CrossProduct(V[st[t][head[t] - 1]], V[st[t][head[t]]], V[i]) <= 0)
            vis[t][st[t][head[t] --]] = false;
        st[t][++ head[t]] = i;
        vis[t][i] = true;
    }
    ll A[2] = {0, 0};
    if (head[0] < 3 || head[1] < 3 || (head[0] + head[1] != n))
        return inf + 1;
    if (sol[0][1] == 'V')
        for (int i = 1; i <= n; ++ i)
            if (sol[0][i] == 'V') sol[0][i] = 'I';
            else sol[0][i] = 'V';
    for (int t = 0; t < 2; ++ t)
    {
        st[t][head[t] + 1] = st[t][1];
        for (int i = 1; i <= head[t]; ++ i)
            A[t] += Det(V[st[t][i]], V[st[t][i + 1]]);
        A[t] = abs(A[t]);
    }
    return abs(A[0] - A[1]);
}
bool lex()
{
    for (int i = 1; i <= n; ++ i)
        if (sol[0][i] != sol[1][i])
            return sol[0][i] < sol[1][i];
    return false;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d%d", &V[i].x, &V[i].y);
        V[i].id = i;
    }
    sort(V + 1, V + n + 1);

    ans = inf;

    for (int a = 1; a < n; ++ a)
        for (int b = 1 + a; b <= n; ++ b)
        {
            ll A = HullDif(a, b);
            if (A < ans || (A == ans && lex()))
            {
                ans = A;
                memcpy(sol[1], sol[0], sizeof(sol[0]));
            }
        }
    if (ans & 1)
        printf("%lld.5\n", ans / 2);
    else
        printf("%lld.0\n", ans / 2);

    for (int i = 1; i <= n; ++ i)
        printf("%c", sol[1][i]);
    return 0;
}