Cod sursa(job #1826988)

Utilizator zhm248Mustatea Radu zhm248 Data 11 decembrie 2016 11:59:06
Problema Gradina Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.82 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long minim=(1LL<<62);
struct punct
{
    int x,y,z;
};

punct v[251],v1[251],v2[251];
char sol1[251],sol[251];
bool cmp(punct a,punct b)
{
    if(a.y==b.y)
        return a.x<b.x;
    else
        return a.y<b.y;
}

long long cp(punct a,punct b,punct c)
{
    return 1LL*a.x*b.y-1LL*a.y*b.x+1LL*b.x*c.y-1LL*b.y*c.x+1LL*c.x*a.y-1LL*c.y*a.x;
}

int ccw(punct a,punct b,punct c)
{
    if(cp(a,b,c)>0)
        return 1;
    if(cp(a,b,c)<0)
        return -1;
    return 0;
}

bool cmp1(punct a,punct b)
{
    return ccw(v1[1],a,b)>0;
}

bool cmp2(punct a,punct b)
{
    return ccw(v2[1],a,b)>0;
}

int main()
{
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    int n,i,j,k,nr1,nr2;
    long long arie1,arie2;
    scanf("%d",&n);
    for(i=1; i<=n; ++i)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
        v[i].z=i;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=n; ++j)
        {
            if(i!=j)
            {
                nr1=0;
                nr2=0;
                for(k=1; k<=n; ++k)
                {
                    if(ccw(v[i],v[j],v[k])>0||k==i)
                    {
                        v1[++nr1]=v[k];
                        sol1[v[k].z]='I';
                    }
                    else
                    {
                        v2[++nr2]=v[k];
                        sol1[v[k].z]='V';
                    }
                }
                if(nr1>=3&&nr2>=3)
                {
                    sort(v1+2,v1+nr1+1,cmp1);
                    sort(v2+2,v2+nr2+1,cmp2);
                    bool ok=1;
                    for(k=3; k<=nr1; ++k)
                    {
                        if(ccw(v1[k-2],v1[k-1],v1[k])<1)
                        {
                            ok=0;
                            break;
                        }
                    }
                    if(ccw(v1[nr1-1],v1[nr1],v1[1])<1)
                        ok=0;
                    if(ccw(v1[nr1],v1[1],v1[2])<1)
                        ok=0;
                    if(ok)
                    {
                        for(k=3; k<=nr2; ++k)
                        {
                            if(ccw(v2[k-2],v2[k-1],v2[k])<1)
                            {
                                ok=0;
                                break;
                            }
                        }
                        if(ccw(v2[nr2-1],v2[nr2],v2[1])<1)
                            ok=0;
                        if(ccw(v2[nr2],v2[1],v2[2])<1)
                            ok=0;
                        if(ok)
                        {
                            if(sol1[1]=='V')
                            {
                                for(k=1; k<=n; ++k)
                                {
                                    if(sol1[k]=='V')
                                        sol1[k]='I';
                                    else
                                        sol1[k]='V';
                                }
                            }
                            arie1=0;
                            arie2=0;
                            for(k=1; k<nr1; ++k)
                            {
                                arie1+=(1LL*v1[k].x*v1[k+1].y);
                                arie1-=(1LL*v1[k].y*v1[k+1].x);
                            }
                            arie1+=(1LL*v1[nr1].x*v1[1].y);
                            arie1-=(1LL*v1[1].x*v1[nr1].y);
                            if(arie1<0)
                                arie1*=(-1);
                            for(k=1; k<nr2; ++k)
                            {
                                arie2+=(1LL*v2[k].x*v2[k+1].y);
                                arie2-=(1LL*v2[k].y*v2[k+1].x);
                            }
                            arie2+=(1LL*v2[nr2].x*v2[1].y);
                            arie2-=(1LL*v2[1].x*v2[nr2].y);
                            if(arie2<0)
                                arie2*=(-1);
                            long long arie=arie1-arie2;
                            if(arie<0)
                                arie*=(-1);
                            if(arie<minim)
                            {
                                minim=arie;
                                for(k=1; k<=n; ++k)
                                {
                                    sol[k]=sol1[k];
                                }
                            }
                            else
                            {
                                if(arie==minim)
                                {
                                    bool ok2=0;
                                    for(k=1; k<=n; ++k)
                                    {
                                        if(sol1[k]<sol[k])
                                        {
                                            ok2=1;
                                            break;
                                        }
                                    }
                                    if(ok2)
                                    {
                                        for(k=1; k<=n; ++k)
                                        {
                                            sol[k]=sol1[k];
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    if(minim%2==0)
        printf("%lld.0\n",minim/2);
    else
        printf("%lld.5\n",minim/2);
    for(i=1; i<=n; ++i)
    {
        printf("%c",sol[i]);
    }
    return 0;
}