Cod sursa(job #213431)

Utilizator CezarMocanCezar Mocan CezarMocan Data 9 octombrie 2008 19:55:54
Problema Gradina Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.46 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;

int a1, a2, rez, fb;

double finn;

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


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

inline int 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;
}

bool bun(punct a, punct b, punct c){
	if (a.x*b.y+b.x*c.y+c.x*a.y<=c.x*b.y+b.x*a.y+a.x*c.y)
		return true;
	else
		return false;
}	


int arie(punct vv[])
{
    int 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 abs(a);        
}

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()
{
     int k; 
     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=abs(a1-a2);
     
     if ((vf1-1)!=nr1||(vf2-1)!=nr2)
        fb=1999999999;
                 
     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();
              
                
            sol[v[i].p]=2;
            sol[v[j].p]=1;
                 
            nr1=nr2=0;     
                 
               nr1=nr2=0;
               sol[v[i].p]=2;
               sol[v[j].p]=1;
               
               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)
                        {
                            nr2++;
                            v2[nr2]=v[k];    
                        }
                        else
                        {
                            nr1++;
                            v1[nr1]=v[k];    
                        }
            if (nr1>=3&&nr2>=3)
                scula();
                 
            }

    finn=1.0*rez/2;

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

    printf("\n");

return 0;    
}