Cod sursa(job #176738)

Utilizator sealTudose Vlad seal Data 11 aprilie 2008 16:45:53
Problema Gradina Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
using namespace std;
#include<cstdio>
#include<algorithm>
#define Nm 256
#define Inf (1ll<<60)
#define ll long long
#define abs(a) ((a)<0?-(a):(a))
char S[Nm],Ans[Nm];
int X[Nm],Y[Nm],n;
ll ans;

void read()
{
    int i;
    
    freopen("gradina.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%d%d",X+i,Y+i);
}

bool cmp(int a, int b)
{
    return Y[a]<Y[b];
}

ll cross(int x0, int y0, int x1, int y1, int x2, int y2)
{
    return (ll)(x1-x0)*(y2-y0)-(ll)(x2-x0)*(y1-y0);
}

ll convex(int A[], int a)
{
    int P[Nm],L[Nm],R[Nm],i,l=0,r=0,p=0;
    ll area=0,c;

    for(i=1;i<a-1;++i)
        if(cross(X[A[0]],Y[A[0]],X[A[a-1]],Y[A[a-1]],X[A[i]],Y[A[i]])<0) L[++l]=A[i];
        else R[++r]=A[i];
        
    P[p++]=A[0];
    for(i=1;i<=l;++i) P[p++]=L[i];
    P[p++]=A[a-1];
    for(i=r;i;--i) P[p++]=R[i];

    for(i=1;i<a-1;++i)
    {
        c=cross(X[P[0]],Y[P[0]],X[P[i]],Y[P[i]],X[P[i+1]],Y[P[i+1]]);
        if(c<0) return 0;
        area+=c;
    }
    return area;
}

void doit(int A[], int a, int B[], int b)
{
    int i;
    ll x,y;
    
    if(a<3 || b<3) return;
    x=convex(A,a);
    if(!x) return;
    y=convex(B,b);
    if(!y) return;
    if(abs(x-y)>ans) return;

    for(i=0;i<a;++i) S[A[i]]='I';
    for(i=0;i<b;++i) S[B[i]]='V';
    if(S[0]=='V')
        for(i=0;i<n;++i) S[i]=S[i]=='I'?'V':'I';
    if(abs(x-y)<ans || memcmp(S,Ans,n)<0)
        ans=abs(x-y), memcpy(Ans,S,n);
}

void solve()
{
    int P[Nm],A1[Nm],B1[Nm],A2[Nm],B2[Nm],i,j,k,a1,b1,a2,b2;

    for(i=0;i<n;++i) P[i]=i;
    sort(P,P+n,cmp);

    i=cross(2,1,5,1,8,2)+cross(2,1,8,2,12,4);
    for(ans=Inf,i=0;i<n;++i)
        for(j=i+1;j<n;++j)
        {
            a1=b1=a2=b2=0;
            for(k=0;k<n;++k)
            {
                if(k==i) { A1[a1++]=B2[b2++]=P[i]; continue; }
                if(k==j) { A2[a2++]=B1[b1++]=P[j]; continue; }
                if(cross(X[P[i]],Y[P[i]],X[P[j]],Y[P[j]],X[P[k]],Y[P[k]])<0)
                    A1[a1++]=A2[a2++]=P[k];
                else
                    B1[b1++]=B2[b2++]=P[k];
            }
            doit(A1,a1,B1,b1);
            doit(A2,a2,B2,b2);
        }
}

void write()
{
    freopen("gradina.out","w",stdout);
    printf("%.1lf\n%s\n",(double)ans/2,Ans);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}