Cod sursa(job #67717)

Utilizator mariusdrgdragus marius mariusdrg Data 25 iunie 2007 13:39:06
Problema Gradina Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 6.2 kb
#include<algorithm>

#include<stdio.h>

using namespace std;

const int maxn = 501;

typedef int sir[maxn];


double x[maxn];
double y[maxn];
int n;
int i;
int j;
int k;
sir st[3];
sir sti;
sir ans;
sir ver;
double sol;

double modul(double x)
{
        return x > 0 ? x : -x;
}

bool dr(int i,int j,int p1,int p2)
{
        if ((x[i] * y[j] + x[j] * y[p1] + x[p1] * y[i] - y[i] * x[j] - y[j] * x[p1] - y[p1] * x[i]  < 0) != (x[i] * y[j] + x[j] * y[p2] + x[p2] * y[i] - y[i] * x[j] - y[j] * x[p2] - y[p2] * x[i]  < 0)) return 0;
        return 1;
}

double unghi(int i,int j)
{
        if (y[j] - y[i] == 0) return 1000000;
        return x[i] - x[j] / y[i] - y[j];
}

bool cmpf(const int i,const int j)
{
        return x[i] < x[j];
}

double convex_hull(sir &x1)
{
        int i;
        memset(ver,0,sizeof(ver));
        memset(sti,0,sizeof(sti));
        sort(x1 + 1,x1 + x1[0] + 1,cmpf);
        sti[0]++;
        sti[sti[0]] = x1[1];
        sti[0]++;
        ver[x1[1]] = 1;
        ver[x1[2]] = 1;
        sti[sti[0]] = x1[2];

        for(i = 3;i <= x1[0]; ++i)
        {
                while(modul(unghi(sti[sti[0] - 1],sti[sti[0]])) < modul(unghi(sti[sti[0] -1],x1[i])) &&  sti[0] >= 2 )
                {
                        ver[sti[sti[0]]] = 0;
                        sti[0]--;
                }
                sti[0]++;
                sti[sti[0]] = x1[i];
                ver[x1[i]] = 1;
        }
        int aux = sti[0];
        for(i = x1[0]; i; --i)
        {
                if (!ver[x1[i]])
                {
                        sti[0]++;
                        sti[sti[0]] = x1[i];
                }
                if (sti[0] - aux >= 2 && (unghi(sti[sti[0] - 2],sti[sti[0] - 1]) > unghi(sti[sti[0] - 2],x1[i])))
                {
                        return -1;
                }
        }
        double arie = 0;
        sti[0]++;
        sti[sti[0]] = sti[1];
        for(i = 1;i <= sti[0]; ++i)
        {
                arie += x[sti[i]] * y[sti[i + 1]] - x[sti[i + 1]] * y[sti[i]];
        }
        return modul(arie);
        
}


int main()
{
        freopen("gradina.in","r",stdin);
        freopen("gradina.out","w",stdout);
        scanf("%d",&n);
        for(i = 1;i <= n; ++i)
        {
                scanf("%lf %lf",&x[i],&y[i]);
        }
        sol = 1000000;
        for(i = 1;i <= n; ++i)
        {
                for(j = i + 1;j <= n; ++j)
                {
                        memset(st,0,sizeof(st));
                        for(k = 1;k <= n; ++k)
                        {
                                if (k == i || k == j)  continue;
                                if (dr(i,j,k,st[1][1]) || st[1][0] == 0)
                                {
                                        st[1][0]++;
                                        st[1][st[1][0]] = k;
                                }
                                else
                                {
                                        st[2][0]++;
                                        st[2][st[2][0]] = k;
                                }
                        }
                        for(k = 1;k <= 2; ++k)
                        {
                                st[k][0]++;
                                st[k][st[k][0]] = i;
                                st[k][0]++;
                                st[k][st[k][0]] = j;
                                double o1 = convex_hull(st[1]);
                                double o2 = convex_hull(st[2]);
                                if (o1 != -1 && o2 != -1)
                                {
                                       if (sol > modul(o1 - o2))
                                       {
                                                sol = modul(o1 - o2);
                                                int i1;
                                                memset(ans,0,sizeof(ans));
                                                for(i1 = 1;i1 <= st[1][0]; ++i1)
                                                        ans[st[1][i1]] = 1;
                                       }
                                }
                                int i1;
                                for(i1 = 1;i1 <= st[k][0]; ++i1)
                                {
                                        if (st[k][i1] == i)
                                        {
                                                break;
                                        }
                                }
                                for(;i1 <= st[k][0]; ++i1)
                                {
                                        st[k][i1] = st[k][i1 + 1];
                                }
                                for(i1 = 1;i1 <= st[k][0]; ++i1)
                                {
                                        if (st[k][i1] == j)
                                        {
                                                break;
                                        }
                                }
                                for(;i1 <= st[k][0]; ++i1)
                                {
                                        st[k][i1] = st[k][i1 + 1];
                                }
                                st[k][0] -= 2;
                        }
                }
        }
        printf("%.1lf\n",sol);
        int veri = 0;
        if (ans[1] == 1) veri = 1;
        for(i = 1;i <= n; ++i)
        {
                if (ans[i])
                {
                        if (veri)
                        {
                                printf("I");
                        }
                        else
                        {
                                printf("V");
                        }
                }
                else
                {
                        if (veri)
                        {
                                printf("V");
                        }
                        else
                        {
                                printf("I");
                        }
                }
        }
        printf("\n");
        return 0;
}