Cod sursa(job #69466)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 3 iulie 2007 10:25:19
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <stdio.h>
#include <algorithm>
#include <string>

using namespace std;

#define maxn 260
#define maxl 2
#define maxv 100000000000LL
#define maxarie 10000000000000000LL
#define ld long double
#define ll long long
#define det(x1,y1,x2,y2) (1LL*x1*y2-1LL*x2*y1)
#define Cross_Product(x1,x2,x3,y1,y2,y3) (1LL*(x2-x1)*(y3-y1)-1LL*(x3-x1)*(y2-y1))

int n,m,l;
int a[maxn],b[maxn],p[maxn],p2[maxn];
char rez[maxn],c[maxn],op[maxn];
int x[maxn],y[maxn],sx[maxn],sy[maxn];
int nr[maxl];
ll sol;

int cmp(int x,int y)
{
    return (b[x]<b[y]) || ((b[x]==b[y]) && (a[x]<a[y]));
}

int cmp2(int x,int y)
{
    return (b[x]>b[y]) || ((b[x]==b[y]) && (a[x]>a[y]));
}

void Graham_Scan(char col,int p[])
{
     int i;
     ll aux;
     l=0;
     
     for (i=1;i<=n;i++)
       if (c[p[i]]==col)
       {
            if (l>1) 
            {
                 aux=Cross_Product(x[l-1],x[l],a[p[i]],y[l-1],y[l],b[p[i]]);
                 while ((aux<=0) && (l>1)) 
                 {
                       l--;
                       aux=Cross_Product(x[l-1],x[l],a[p[i]],y[l-1],y[l],b[p[i]]);
                 }
            }
            l++;
            x[l]=a[p[i]];
            y[l]=b[p[i]];
            
       }
}

void opposite(char a[],char b[])
{
     int i;
     for (i=1;i<=n;i++) 
       if (a[i]=='I') b[i]='V';
       else b[i]='I';
}

int strcomp(char a[],char b[])
{
    for (int i=1;i<=n;i++)
      if (a[i]!=b[i]) return a[i]<b[i];
      
    return 0;
}

ll Convex_Hull(char col,int z)
{
      int i;
      ll rez=0;
      m=0;
                    
      Graham_Scan(col,p);
      for (i=1;i<l;i++) 
      {
          m++;
          sx[m]=x[i];
          sy[m]=y[i];
      }
      
      Graham_Scan(col,p2);
      for (i=1;i<l;i++)
      {
          m++;
          sx[m]=x[i];
          sy[m]=y[i];
      }
      
      if ((m<3) || (m!=z)) return -1;
      
      sx[m+1]=sx[1];
      sy[m+1]=sy[1];
      
      for (i=1;i<=m;i++) rez+=det(sx[i],sy[i],sx[i+1],sy[i+1]);
      return abs(rez);
}

int main()
{
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    
    scanf("%d ",&n);
    
    int i,j,k;
    ld m1,n1;
    ll a1,a2;
    sol=maxarie;
    
    for (i=1;i<=n;i++) 
    {
        scanf("%d %d ",&a[i],&b[i]);
        p[i]=i;
        p2[i]=i;
    }
        
    sort(p+1,p+n+1,cmp);
    sort(p2+1,p2+n+1,cmp2);
    
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        if (i!=j)
        {
             nr[0]=1;
             nr[1]=1;
             c[i]='I';
             c[j]='V';
             for (k=1;k<=n;k++) 
               if ((i!=k) && (j!=k)) 
                  if (Cross_Product(a[i],a[j],a[k],b[i],b[j],b[k])<0) 
                  {
                      c[k]='I';
                      nr[0]++;
                  }
                  else {
                            c[k]='V';
                            nr[1]++;
                       }
                       
             a1=Convex_Hull('I',nr[0]);
             a2=Convex_Hull('V',nr[1]);
             
             opposite(c,op);
             if (strcomp(op,c)) memcpy(c,op,sizeof(op));
             
             if ((a1!=-1) && (a2!=-1)) 
             {
                  if ((abs(a2-a1)<sol) || ((abs(a2-a1)==sol) && (strcomp(c,rez))))
                  {
                        sol=abs(a2-a1);
                        memcpy(rez,c,sizeof(rez));
                  }
             }
        }
        
    printf("%.1lf\n",1.0*sol/2);
    for (i=1;i<=n;i++) printf("%c",rez[i]);
    printf("\n");
    
    return 0;
}