Cod sursa(job #592964)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 31 mai 2011 18:27:10
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 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 v[maxn], st[maxn];
long long a1, a2, ns, sol;
pair<int, int> p[maxn];
int xc, yc;

inline int cmp(int a, int b)
{
    return atan2(p[a].second-yc, p[a].first-xc)<atan2(p[b].second-yc, p[b].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()
{
    for(int i=2; i<=v[0]; ++i)
        if(p[v[i]]<p[v[1]])
            swap(v[1], v[i]);

    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>3 && 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);
}


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=1; j<=n; ++j)
        {
            if(i==j)
                continue;

            v[0]=0;
            for(int k=1; k<=n; ++k)
            {
                if(i==k || j==k)
                    continue;
                if(det(i, j, k)<0)
                    v[++v[0]]=k;
            }
            v[++v[0]]=i;
            a1=solve();

            v[0]=0;
            for(int k=1; k<=n; ++k)
            {
                if(i==k || j==k)
                    continue;
                if(det(i, j, k)>0)
                    v[++v[0]]=k;
            }
            v[++v[0]]=j;
            a2=solve();

            ns=ab(a1-a2);
            if(ns<sol)
            {
                sol=ns;
                memset(conf, 0, sizeof(conf));
                for(int k=1; k<=v[0]; ++k)
                    conf[v[k]]=1;
            }
            else
            if(ns==sol)
            {
                memset(cand, 0, sizeof(cand));
                for(int k=1; k<=v[0]; ++k)
                    cand[v[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];
            }
        }

    printf("%.1lf\n", 1.0*sol/2);
    for(int i=1; i<=n; ++i)
        if(conf[i])
            printf("V");
        else
            printf("I");
    printf("\n");

    return 0;
}