Cod sursa(job #592991)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 31 mai 2011 19:25:30
Problema Gradina Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.89 kb
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <utility>

using namespace std;

#define maxn 255
#define inf (1LL*1000000000*1000000000)

int n, ok, conf[maxn], cand[maxn];
int st[maxn];
long long a1, a2, ns, sol;
pair<int, int> p[maxn];
int xc, yc, v1[maxn], v2[maxn];
double tg[maxn];

inline int cmp(int a, int b)
{
    return 1LL*(p[a].second-yc)*(p[b].first-xc)<1LL*(p[b].second-yc)*(p[a].first-xc);
}

long long ab(long long a)
{
    if(a>0)
        return a;
    return -a;
}

int det(int a, int b, int c)
{
    long long ar=1LL*p[a].first*p[b].second+1LL*p[b].first*p[c].second+1LL*p[c].first*p[a].second-
                (1LL*p[b].first*p[a].second+1LL*p[c].first*p[b].second+1LL*p[a].first*p[c].second);

    if(ar==0)
        return 0;
    if(ar>0)
        return 1;
    return -1;
}

long long solve(int v[])
{
    for(int i=2; i<=v[0]; ++i)
        if(p[v[i]]<p[v[1]])
            swap(v[1], v[i]);

    xc=p[v[1]].first;
    yc=p[v[1]].second;

    sort(v+2, v+v[0]+1, cmp);

    int st0=0;
    for(int i=1; i<=v[0]; ++i)
    {
        st[++st0]=v[i];
        while(st0>2 && det(st[st0-2], st[st0-1], st[st0])==-1)
        {
            --st0;
            st[st0]=st[st0+1];
        }
    }

    st[st0+1]=st[1];

    long long ar=0;

    for(int i=1; i<=st0; ++i)
        ar+=1LL*p[st[i]].first*p[st[i+1]].second-1LL*p[st[i+1]].first*p[st[i]].second;

    return ab(ar);
}

void verif()
{
    if(ns<sol)
    {
        sol=ns;
        memset(conf, 0, sizeof(conf));
        for(int k=1; k<=v2[0]; ++k)
            conf[v2[k]]=1;
    }
    else
    if(ns==sol)
    {
        memset(cand, 0, sizeof(cand));
        for(int k=1; k<=v2[0]; ++k)
            cand[v2[k]]=1;

        ok=0;
        for(int k=1; k<=n; ++k)
        {
            if(cand[k]<conf[k])
            {
                ok=1;
                break;
            }
            if(cand[k]>conf[k])
                break;
        }

        if(ok)
            for(int k=1; k<=n; ++k)
                conf[k]=cand[k];

        memset(cand, 0, sizeof(cand));
        for(int k=1; k<=v1[0]; ++k)
            cand[v1[k]]=1;

        ok=0;
        for(int k=1; k<=n; ++k)
        {
            if(cand[k]<conf[k])
            {
                ok=1;
                break;
            }
            if(cand[k]>conf[k])
                break;
        }

        if(ok)
            for(int k=1; k<=n; ++k)
                conf[k]=cand[k];
    }
}

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

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%d%d", &p[i].first, &p[i].second);

    sol=inf;

    for(int i=1; i<=n; ++i)
        for(int j=i+1; j<=n; ++j)
        {
            v1[0]=v2[0]=0;
            for(int k=1; k<=n; ++k)
            {
                if(i==k || j==k)
                    continue;
                if(det(i, j, k)<0)
                    v1[++v1[0]]=k;
                else
                    v2[++v2[0]]=k;
            }
            v1[++v1[0]]=j;
            v2[++v2[0]]=i;

            if(v1[0]<3 || v2[0]<3)
                continue;

            a1=solve(v1);
            a2=solve(v2);

            ns=ab(a1-a2);

            verif();

            v1[0]=v2[0]=0;
            for(int k=1; k<=n; ++k)
            {
                if(i==k || j==k)
                    continue;
                if(det(i, j, k)<0)
                    v1[++v1[0]]=k;
                else
                    v2[++v2[0]]=k;
            }
            v1[++v1[0]]=i;
            v2[++v2[0]]=j;

            if(v1[0]<3 || v2[0]<3)
                continue;

            a1=solve(v1);
            a2=solve(v2);

            ns=ab(a1-a2);

            verif();
        }

    if(sol%2)
        printf("%lld.5\n", sol/2);
    else
        printf("%lld.0\n", sol/2);

    for(int i=1; i<=n; ++i)
        if(conf[i])
            printf("V");
        else
            printf("I");
    printf("\n");

    return 0;
}