Cod sursa(job #2000638)

Utilizator akaprosAna Kapros akapros Data 14 iulie 2017 12:03:32
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <bits/stdc++.h>
#define maxN 252
#define inf 2000000000000000000LL
using namespace std;

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

/* ---------------------------------------- */
int n;
struct Point
{
    int x, y, idx;
    bool operator < (const Point &ot) const
    {
        if (x == ot.x)
            return y < ot.y;
        return x < ot.x;
    }
} v[maxN];
/* ---------------------------------------- */
int P[2][maxN], st[maxN];
bool vis[maxN];
long long Area[2];
/* ---------------------------------------- */
long long ans;
char a[maxN], b[maxN];

bool Lex()
{
    for (int i = 1; i <= n; ++ i)
        if (a[i] != b[i])
            return a[i] > b[i];
    return 0;
}

bool 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) <= 0LL;
}

bool sep(int i, int j, int p)
{
    long long a = v[i].y - v[j].x,
              b = v[j].x - v[i].x,
              c = 1LL * v[i].x * v[j].y - 1LL * v[i].y * v[j].x;
    return 1LL * a * v[p].x + 1LL * b * v[p].y + c > 0;
}

void SepP(int i, int j)
{
    P[0][0] = P[1][0] = 0;
    for (int p = 1; p <= n; ++ p)
        if (i != p && j != p)
        {
            if (sep(i, j, p))
            {
                P[0][++ P[0][0]] = p;
                b[v[p].idx] = 'I';
            }
            else
            {
                P[1][++ P[1][0]] = p;
                b[v[p].idx] = 'V';
            }
        }
        else if (i == p)
        {
            P[0][++ P[0][0]] = p;
            b[v[p].idx] = 'I';
        }
        else
        {
            P[1][++ P[1][0]] = p;
            b[v[p].idx] = 'V';
        }
}
int ConvexHull(int t)
{
    st[0] = 2;
    st[1] = 1;
    st[2] = 2;
    memset(vis, 0, sizeof(vis));
    vis[2] = 1;
    for (int i = 3, p = 1; i > 0; i += p)
    {
        if (!vis[i])
        {
            while (st[st[0]] != P[t][0] && st[0] >= 2 && CrossProduct(v[P[t][st[st[0] - 1]]], v[P[t][st[st[0]]]], v[P[t][i]]))
                vis[st[st[0] --]] = 0;
            st[++ st[0]] = i;
            vis[i] = 1;
        }
        if (i == P[t][0])
            p = -1;
    }
    st[st[0]] = st[1];
    Area[t] = 0;
    for (int i = 1; i < st[0]; ++ i)
        Area[t] += 1LL * v[P[t][st[i]]].x * v[P[t][st[i + 1]]].y - 1LL * v[P[t][st[i]]].y * v[P[t][st[i + 1]]].x;
    Area[t] = abs(Area[t]);
    return st[0] - 1;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &v[i].x, &v[i].y);
        v[i].idx = i;
    }
    ans = inf;

    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            if (i != j)
            {
                SepP(i, j);
                if (P[0][0] < 3 || P[1][0] < 3)
                    continue;
                for (int t = 0; t < 2; ++ t)
                    if (ConvexHull(t) != P[t][0])
                        break;
                    else if (t)
                    {
                        if ((ans > abs(Area[0] - Area[1])) || ((ans == abs(Area[0] - Area[1])) && Lex()))
                        {
                            memcpy(a, b, sizeof(b));
                            ans = abs(Area[0] - Area[1]);
                        }
                    }
            }

    for (int i = 1; i <= n; ++ i)
        b[i] = 'I' + 'V' - a[i];
    if (Lex())
        memcpy(a, b, sizeof(b));

    printf("%lld.%d\n", ans / 2, 5 * (ans % 2));
    for (int i = 1; i <= n; ++ i)
        printf("%c", a[i]);
    return 0;
}