Cod sursa(job #213440)

Utilizator CezarMocanCezar Mocan CezarMocan Data 9 octombrie 2008 20:17:05
Problema Gradina Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.98 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];

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

double a1, a2, rez;

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

bool mai_bun()
{
    long i=1;
    
    while ((sol[i]==fin[i])&&(i<=n))
        i++;
        
    if (sol[i]<fin[i])
        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;
}

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];    
    }

    
}

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

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;
    }
        
    sort(v+1, v+n+1, cmp);
    
    rez=2000000000;
    
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i!=j)
            {
            //fac p'acolo infasuratoarea in O(n) presupunand ca punctul i intra in poligonu din stanga si
            //j intra in ala din dreapta... simplu :P Teorema saxifuzului :))
            
            nr1=nr2=0;
            
            for (k=1;k<=n;k++)
            {
                if ( saxifuz(v[i], v[j], v[k]) > 0 )
                {
                    nr1++;
                    v1[nr1]=v[k];  
                }
                
                if ( saxifuz(v[i], v[j], v[k]) < 0 )
                {
                    nr2++;
                    v2[nr2]=v[k];    
                }
                
                if (k==i)
                {
                   nr1++;
                   v1[nr1]=v[k];      
                }
                   
                if (k==j)
                {
                   nr2++;
                   v2[nr2]=v[k];
                }
                
            }
                    
            if ((nr1>=3)&&(nr2>=3))
            {
               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);   
                             
               for (k=1;k<=n;k++)
               {
                   if ( saxifuz(v[i], v[j], v[k]) > 0 )
                      sol[v[k].p]=1;
                      
                   if ( saxifuz(v[i], v[j], v[k]) < 0 )
                       sol[v[k].p]=2; 
                       
                   if (k==i)
                      sol[v[k].p]=1;                   
                   if (k==j)
                      sol[v[k].p]=2;
                }
            
               if (fabs(a1-a2)==rez)              
               {
                    if (mai_bun())
                        for (k=1;k<=n;k++)
                            fin[k]=sol[k];     
               }
            
               if (fabs(a1-a2)<rez)  
               {    
                  rez=fabs(a1-a2);
                  
                  for (k=1;k<=n;k++)
                     fin[k]=sol[k];
               }
               
            }
               
               
            nr1=nr2=0;
            
            for (k=1;k<=n;k++)
            {
                if ( saxifuz(v[i], v[j], v[k]) > 0 )
                {
                    nr1++;
                    v1[nr1]=v[k];  
                }
                
                if ( saxifuz(v[i], v[j], v[k]) < 0 )
                {
                    nr2++;
                    v2[nr2]=v[k];    
                }
                
                if (k==j)
                {
                   nr1++;
                   v1[nr1]=v[k];      
                }
                   
                if (k==i)
                {
                   nr2++;
                   v2[nr2]=v[k];
                }
                
            }
                    
            if ((nr1>=3)&&(nr2>=3))
            {
               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);   
                             
               for (k=1;k<=n;k++)
               {
                   if ( saxifuz(v[i], v[j], v[k]) > 0 )
                      sol[v[k].p]=1;
                      
                   if ( saxifuz(v[i], v[j], v[k]) < 0 )
                       sol[v[k].p]=2; 
                       
                   if (k==j)
                      sol[v[k].p]=1;                   
                   if (k==i)
                      sol[v[k].p]=2;
                }
            
               if (fabs(a1-a2)==rez)              
               {
                    if (mai_bun())
                        for (k=1;k<=n;k++)
                            fin[k]=sol[k];     
               }
            
               if (fabs(a1-a2)<rez)  
               {    
                  rez=fabs(a1-a2);
                  
                  for (k=1;k<=n;k++)
                     fin[k]=sol[k];
               }
               
            }
               
               
            }
            
    printf("%.1f\n",rez);
    
   for (i=1;i<=n;i++)
        if (fin[i]==1)
            printf("I");
        else
            printf("V");

    printf("\n");
    return 0;
}