Cod sursa(job #1336013)

Utilizator heracleRadu Muntean heracle Data 6 februarie 2015 12:51:43
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.93 kb
#include <cstdio>
#include <algorithm>

FILE* in=fopen("gradina.in","r");
FILE* out=fopen("gradina.out","w");


const int Q=260,INF=2000000000;
int n;

struct point{
    int x,y;
} v[Q];

void swap(int &a, int &b)
{
    a^=b;
    b^=a;
    a^=b;
}

long long arie(int t[])
{
    long long rez=0;

    long long low=INF;

    for(int i=1; i<=t[0]; i++)
    {
        if(v[t[i]].y<low)
            low=v[t[i]].y;
    }

    for(int i=2; i<=t[0]; i++)
    {
        rez+=(long long)(v[t[i-1]].y-low+v[t[i]].y-low)*(v[t[i]].x-v[t[i-1]].x);
    }

    rez+=(long long)(v[t[t[0]]].y-low+v[t[1]].y-low)*(v[t[1]].x-v[t[t[0]]].x);

    return rez;
}

point eta;

bool clock(point a, point b, point c)
{
    long long aux;

    aux=(long long)(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);

    return aux>0;
}

bool cmp(const int &a,const int &b)
{
    return clock(v[a],v[b],eta);
}

int stv[Q];

bool infas(int t[])
{
    eta.x=INF;
    for(int i=1; i<=t[0]; i++)
    {
        if(v[t[i]].x<eta.x)
        {
            eta.x=v[t[i]].x;
            eta.y=v[t[i]].y;
        }
    }
    std::sort(t+1,t+t[0]+1,cmp);

    for(int i=3; i<=t[0]; i++)
    {
        if(!clock(v[t[i-2]],v[t[i-1]],v[t[i]]))
        {
            return 0;
        }
    }
    return 1;
}

int g[2][Q];

int min=INF;

char rez[Q];


void ver_rez()
{
    std::sort(g[0]+1,g[0]+g[0][0]+1);
    std::sort(g[1]+1,g[1]+g[1][0]+1);

    char c[2];

    if(g[0][1]==1)
    {
        c[0]='I';
        c[1]='V';
    }
    else
    {
        c[0]='V';
        c[1]='I';
    }

    int l1=1,l2=1;

    g[0][g[0][0]+1]=INF;
    g[1][g[1][0]+1]=INF;

    bool bun=0;

    for(int nxt=1; nxt<=n; nxt++)
    {
        if(g[0][l1]==nxt)
        {
            if(rez[nxt]=='V')
            {
                bun=1;
                rez[nxt]='I';
            }
        }
        else
        {
            if(rez[nxt]=='I' && bun==0)
            {
                return;
            }
            rez[nxt]='V';
        }
    }
}

void act_rez()
{
    std::sort(g[0]+1,g[0]+g[0][0]+1);
    std::sort(g[1]+1,g[1]+g[1][0]+1);

    char c[2];

    if(g[0][1]==1)
    {
        c[0]='I';
        c[1]='V';
    }
    else
    {
        c[0]='V';
        c[1]='I';
    }

    for(int i=1; i<=g[0][0]; i++)
    {
        rez[g[0][i]]=c[0];
    }
    for(int i=1; i<=g[1][0]; i++)
    {
        rez[g[1][i]]=c[1];
    }
}

int mod(int x)
{
    return x>0?x:-x;
}

void testeaza()
{
    if(infas(g[0]) && infas(g[1]))
    {
        long long a1,a2;

        a1=arie(g[0]);
        a2=arie(g[1]);

        if(mod(a1-a2)<min)
        {
            min=mod(a1-a2);
            act_rez();
        }
        else if(mod(a1-a2)==min)
        {
            ver_rez();
        }

    }
}

void generat(int t, int p)
{
    g[0][0]=0;
    g[1][0]=0;
    long long a,b,c;

    a=v[p].y-v[t].y;
    b=v[t].x-v[p].x;
    c=(long long)v[p].x*v[t].y-(long long)v[t].x*v[p].y;

    for(int i=1; i<=n; i++)
    {
        if(i!=t && i!=p)
        {
            if((long long)a*v[i].x+(long long)b*v[i].y+c>0)
            {
                g[0][++g[0][0]]=i;
            }
            else
            {
                g[1][++g[1][0]]=i;
            }
        }
    }

    g[0][0]++;
    g[1][0]++;

    if(g[0][0]<3 || g[1][0]<3)
        return;

    g[0][g[0][0]]=t;
    g[1][g[1][0]]=p;

    testeaza();

    for(int i=1; i<=g[0][0]; i++)
    {
        if(g[0][i]==t)
        {
            g[0][i]=p;
            break;
        }
    }
    for(int i=1; i<=g[1][0]; i++)
    {
        if(g[1][i]==p)
        {
            g[1][i]=t;
            break;
        }
    }

    testeaza();

}

int main()
{
    fscanf(in,"%d",&n);

    for(int i=1; i<=n; i++)
    {
        fscanf(in,"%d%d",&v[i].x,&v[i].y);
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            generat(i,j);
        }
    }

    fprintf(out,"%d",min/2);
    if(min&1)
        fprintf(out,".5");
    else
        fprintf(out,".0");
    fprintf(out,"\n");
    fputs(rez+1,out);

    return 0;
}