Cod sursa(job #213257)

Utilizator CezarMocanCezar Mocan CezarMocan Data 8 octombrie 2008 23:34:38
Problema Gradina Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.74 kb
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>


using namespace std;

struct punct{int x; int y; int p;};

punct v[255], v1[255], v2[255], aux;

int n, i, j, st1[255], vf1, st2[255], vf2, nr1, nr2, k, ppi, ppj;

double a1, a2, rez, fb;

int sol[255], fin[255], nr, x[255];


bool cmp(punct a, punct b)
{
    if ((a.x<b.x)||((a.x==b.x)&&(a.y<=b.y)))    
        return true;
    else
        return false;
}

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

double arie(punct vv[])
{
    double a=0;
    int i;
    for (i=1;i<nr;i++)
        a=a+vv[x[i]].x*vv[x[i+1]].y-vv[x[i+1]].x*vv[x[i]].y;
    return a/2;        
}

void infasuratoare(punct v[], int &n, int st[], int &vf)
{
    int i, j, s1[255], s2[255], v1, v2;
    
    memset(s1,0,sizeof(s1));
    memset(s2,0,sizeof(s2));
    
    v1=v2=2;
    s1[1]=1;     
    s1[2]=2;
    
    for (i=3;i<=n;i++){
        while ( (v1>1) && (saxifuz( v[s1[v1-1]], v[s1[v1]], v[i] ) <= 0 )  )   
            v1--;
        v1++;
        s1[v1]=i;    
    }
    
    s2[1]=n;
    s2[2]=n-1;
    
    for (i=n-2;i>=1;i--){
        while ( (saxifuz( v[s2[v2-1]], v[s2[v2]], v[i] ) <=0 ) && (v2>1) )
            v2--;
        v2++;
        s2[v2]=i;    
    }
    
    vf=0;
    for (i=1; i<v1; i++){
        vf++;
        st[vf]=s1[i];    
    }
    for (i=1; i<=v2; i++){
        vf++;
        st[vf]=s2[i];    
    }
}

bool mai_bun()
{
    long i=1;
    
    while ((sol[i]==fin[i])&&(i<=n))
        i++;
        
    if (sol[i]<fin[i])
        return true;
    else
        return false;
}

void scula()
{
     infasuratoare(v1, nr1, st1, vf1);
     infasuratoare(v2, nr2, st2, vf2);   
                 
     nr=vf1;
     for (k=1;k<=nr;k++)
         x[k]=st1[k];
             
     a1=arie(v1);
     nr=vf2;
                 
     for (k=1;k<=nr;k++)
         x[k]=st2[k];
     a2=arie(v2);   
                 
     fb=fabs(a1-a2);
                 
     if (fb==rez)
        if (mai_bun())
           for (k=1;k<=n;k++)    
               fin[k]=sol[k];
                 
     if (fb<rez)
     {
        rez=fb;                    
        for (k=1;k<=n;k++)
            fin[k]=sol[k];
     }  
     
}



int main(){
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].x, &v[i].y);
        v[i].p=i;
    }
    
    rez=2000000000;
    sort(v+1, v+n+1, cmp);    
    
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i!=j)
            {
               nr1=nr2=0;
               sol[v[i].p]=1;
               sol[v[j].p]=2;
               
               for (k=1;k<=n;k++)
                   if (k!=i&&k!=j)
                      if (saxifuz(v[i], v[j], v[k])>0)
                      {
                         nr1++;
                         v1[nr1]=v[k];   
                         sol[v[k].p]=1;               
                      }
                      else
                      {
                          nr2++;
                          v2[nr2]=v[k];
                          sol[v[k].p]=2;    
                      }  
                    else
                        if (k==i)
                        {
                            nr1++;
                            v1[nr1]=v[k];    
                            ppi=nr1;
                        }
                        else
                        {
                            nr2++;
                            v2[nr2]=v[k];    
                            ppj=nr2;
                        }
                      
              if ((nr1>=3)&&(nr2>=3))
              {
                 scula();
                 
/*                 printf("%f %f\n",a1,a2);
                 
                 for (k=1;k<=nr1;k++)
                    printf("%d ",v1[k].p);
                 printf("\n");

                 for (k=1;k<=nr2;k++)
                    printf("%d ",v2[k].p);
                 printf("\n\n");*/
            }
              
/*                 aux=v1[ppi];
                 v1[ppi]=v2[ppj];
                 v2[ppj]=aux;*/
            sol[v[i].p]=2;
            sol[v[j].p]=1;
                 
            nr1=nr2=0;     
                 
            for (k=1;k<=n;k++)
            {
                if (k==i)
                {
                    nr2++;
                    v2[nr2]=v[i];    
                }    
                
                if (k==j)
                {
                    nr1++;
                    v1[nr1]=v[j];    
                }
                
                if (k!=i && k!=j)
                {
                    if (sol[v[k].p]==1)    
                    {
                        nr1++;
                        v1[nr1]=v[k];    
                    }
                    else
                    {
                        nr2++;
                        v2[nr2]=v[k];   
                    }
                }
                    
            }
                
                            
            scula();
                 
/*            printf("%f %f\n",a1,a2);
                 
            for (k=1;k<=nr1;k++)
                printf("%d ",v1[k].p);
            printf("\n");

            for (k=1;k<=nr2;k++)
                printf("%d ",v2[k].p);
            printf("\n");*/
                 
                 
                 
            }

    printf("%.1lf\n",rez);
    
    for (i=1;i<=n;i++)
        if (fin[i]==1)
            printf("I");
        else
            printf("V");

    printf("\n");

return 0;    
}