Cod sursa(job #212903)

Utilizator savimSerban Andrei Stan savim Data 7 octombrie 2008 19:30:26
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxl 300
#define infi 2147000000

int n,i,j,a,b,c,k,ind,nr;
int x[maxl],y[maxl],sol[maxl][2];
int init[maxl][2];
int p[maxl][2],v[maxl],inf[maxl];
double tg[maxl],s1,s2,ch,minim=infi,sup;

void ind_det() {

    int x1,y1,x2,y2;

    if (x[i]<x[j]) {
        x1=x[i];y1=y[i];
        x2=x[j];y2=y[j];
    }
    else if (x[i]>x[j]) {
            x1=x[j];y1=y[j];
            x2=x[i];y2=y[i];
         }
         else if (y[i]<y[j]) {
                 x1=x[i];y1=y[i];
                 x2=x[j];y2=y[j];
              }
              else {
                 x1=x[j];y1=y[j];
                 x2=x[i];y2=y[i];
              }
    

    a=y1-y2;
    b=x2-x1;
    c=x1*y2-x2*y1;
}

inline int cmp(int x, int y) {
       if (tg[x]<tg[y]) return true;
       if (tg[x]>tg[y]) return false;
       if (tg[x]==tg[y]) {
          if (p[x][0]>p[y][0]) return true;
          else return false;
       }
}
double sup_inf() {
       
       int i;
       
       tg[1]=-infi;v[1]=1;
       for (i=2; i<=ind; i++) {
           if (p[i][0]-p[1][0]!=0) tg[i]=(double)(p[i][1]-p[1][1])/(p[i][0]-p[1][0]);
           else tg[i]=infi;
           v[i]=i;
       }
       sort(v+1,v+ind+1,cmp);
       
       inf[1]=v[1];inf[2]=v[2];k=2;
       for (i=3; i<=ind; i++) {
           while (k>1 && (p[inf[k]][0]-p[inf[k-1]][0])*(p[v[i]][1]-p[inf[k-1]][1])-
                         (p[v[i]][0]-p[inf[k-1]][0])*(p[inf[k]][1]-p[inf[k-1]][1])<0) {
                 k--;
           }

           inf[++k]=v[i];
           while (k>2 && ((p[inf[1]][0]-p[inf[k]][0])*(p[inf[2]][1]-p[inf[k]][1])-
                          (p[inf[2]][0]-p[inf[k]][0])*(p[inf[1]][1]-p[inf[k]][1]))<0) {
                k--;
           }
       }
       
       if (k!=ind) return -1;
       else {
            sup=p[inf[ind]][0]*p[inf[1]][1]-p[inf[1]][0]*p[inf[ind]][1];
            for (i=1; i<ind; i++)
                sup+=p[inf[i]][0]*p[inf[i+1]][1]-p[inf[i+1]][0]*p[inf[i]][1];
            sup=(double)sup/2;
            return sup;
       }
}

int main() {

    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    
    scanf("%d",&n);
    for (i=1; i<=n; i++) {
        scanf("%d %d",&x[i],&y[i]);
        init[i][0]=x[i];
        init[i][1]=y[i];
    }
        
    for (i=1; i<=n-1; i++)
        for (j=i+1; j<=n; j++) {
            if (x[i]>x[j]) {
               a=x[i];x[i]=x[j];x[j]=a;
               a=y[i];y[i]=y[j];y[j]=a;
            }
            if (x[i]==x[j] && y[i]>y[j]) {
               a=y[i];y[i]=y[j];y[j]=a;
            }
        }

    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if (i!=j) {
               ind_det();

               ind=1;p[ind][0]=x[i];p[ind][1]=y[i];
               for (k=1; k<=n; k++) 
                   if (k!=i && k!=j && a*x[k]+b*y[k]+c<0) {
                      p[++ind][0]=x[k];p[ind][1]=y[k];
                   }
               s1=sup_inf();
               
               ind=1;p[ind][0]=x[j];p[ind][1]=y[j];
               for (k=1; k<=n; k++) 
                   if (k!=i && k!=j && a*x[k]+b*y[k]+c>0) {
                      p[++ind][0]=x[k];p[ind][1]=y[k];
                   }
               s2=sup_inf();
               
               if (s1<s2) {
                   ch=s1;s1=s2;s2=ch;
               }
                   
               if (s1-s2<minim && s1!=-1 && s2!=-1) {
                  minim=s1-s2;nr=ind;
                  for (k=1; k<=ind; k++) {
                      sol[k][0]=p[k][0];
                      sol[k][1]=p[k][1];
                  }
               }
            } 

    printf("%.1lf\n",minim);
    for (i=1; i<=n; i++) {
        a=0;
        for (j=1; j<=nr; j++)
            if (init[i][0]==sol[j][0] && init[i][1]==sol[j][1]) {
               a=1;
               break;
            }
        if (!a) printf("I");
        else printf("V");
    }
    printf("\n");

    return 0;
}