Cod sursa(job #1784018)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 19 octombrie 2016 18:14:45
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAXN 300
#define inf 0x3f3f3f3f

using namespace std;

struct coord
{
    int x, y;
    int ind;
    bool operator()(coord e, coord f)
    {
        if (e.x != f.x) return e.x < f.x;
        return e.y < f.y;
    }
};
coord a[MAXN];
int n;

int det(coord e1, coord e2, coord e3)
{
    return e1.x*e2.y + e2.x*e3.y + e3.x*e1.y - e3.x*e2.y - e2.x*e1.y - e1.x*e3.y;
}

void read()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i].x, &a[i].y);
        a[i].ind = i;
    }
    sort(a+1, a+1+n, coord());
}
vector<coord> poly;
char sol[MAXN], crt[MAXN];

void buildCrt()
{
    for (int i = 1; i <= n; i++)
        crt[i] = 'I';
    for (coord c : poly)
        crt[c.ind] = 'V';
    if (crt[1] == 'V')
        for (int i = 1; i <= n; i++)
            crt[i] = (crt[i] == 'V' ? 'I' : 'V');
}

void add(vector<coord> &sc, coord c)
{
    while (sc.size() >= 2 && det(sc[sc.size()-2], sc.back(), c) > 0)
        sc.pop_back();
    sc.push_back(c);
}

int buildPoly(coord e, coord f, int sus)
{
    poly.clear();
    for (int i = 1; i <= n; i++)
        if ((det(e, f, a[i]) >= 0) == sus)
            poly.push_back(a[i]);
    vector<coord> s1, s2;
    for (int i = 0; i < poly.size(); i++)
        add(s1, poly[i]);
    for (int i = poly.size()-1; i >= 0; i--)
        add(s2, poly[i]);
    for (int i = 1; i < s2.size()-1; i++)
        s1.push_back(s2[i]);
    if (poly.size() != s1.size())
        return 0;
    for (int i = 0; i < poly.size(); i++)
        poly[i] = s1[i];
    return 1;
}

int arie()
{
    if (poly.size() < 3) return 0;
    int to = 0;
    coord au;
    au.x = 0, au.y = 0;
    for (int i = 0; i < poly.size()-1; i++)
        to += det(au, poly[i], poly[i+1]);
    to += det(au, poly.back(), poly.front());
    to = abs(to);
    return to;
}

int better()
{
    for (int i = 1; i <= n; i++)
        if (crt[i] < sol[i])
            return 1;
        else if (sol[i] < crt[i])
            return 0;
}

void solve()
{
    int best = inf;
    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++) {
            int ok = 1;
            ok &= buildPoly(a[i], a[j], 1);
            if (!ok) continue;
            int a1 = arie();
            ok &= buildPoly(a[i], a[j], 0);
            if (!ok) continue;
            int a2 = arie();
            int dif = abs(a1-a2);
            buildCrt();
            if (dif < best || dif == best && better()) {
                best = dif;
                for (int i = 1; i <= n; i++)
                    sol[i] = crt[i];
            }
        }
    printf("%.1lf\n", best/2.0);
    printf("%s", sol+1);
}

int main()
{
    freopen("gradina.in", "r", stdin);
    freopen("gradina.out", "w", stdout);

    read();
    solve();

    return 0;
}