Cod sursa(job #212942)

Utilizator savimSerban Andrei Stan savim Data 7 octombrie 2008 21:28:31
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.34 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;
}