Cod sursa(job #88824)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 4 octombrie 2007 11:51:11
Problema Popandai Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.35 kb
#include <stdio.h>
#include <string.h>
#include <math.h>

#define NMAX 333
#define eps 1e-10
#define INF 666000666

int X[NMAX], Y[NMAX], poz1[NMAX], poz2[NMAX], A[NMAX][NMAX];
int N, K;
double U[NMAX], Area, Up[NMAX], Down[NMAX];

void sortx(long p1,long p2)
{
     int i, j, k, aux, m;
     
     if (p2-p1==1)
     {
       if (X[poz1[p2]]<X[poz1[p1]])
         aux = poz1[p1], poz1[p1] = poz1[p2], poz1[p2]=aux;
     }
     else
     if (p2-p1>1)
     {
            sortx(p1,(p1+p2)>>1);
            sortx(((p1+p2)>>1)+1,p2);
          
            k = p1-1;
            i = p1;
            m = (p1+p2)>>1;
            j = m+1;
          
            while (i<=m && j<=p2)
            {
              k++;
              if (X[poz1[i]]<X[poz1[j]])
              {
                poz2[k] = poz1[i];
                i++;
              }
              else
              {
                poz2[k] = poz1[j];
                j++;
              }
            }
          
            if (i<=m)
            {
              for (j = i; j <= m; j++)
              {
                k++;
                poz2[k] = poz1[j];
              }
            }
            else
            {
              for (i = j; i <= p2; i++)
              {
                k++;
                poz2[k] = poz1[i];
              }
            }
          
            for (k = p1; k <= p2; k++) poz1[k] = poz2[k];
     }
}

void sortu(long p1,long p2)
{
     int i, j, k, aux, m;
     
     if (p2-p1==1)
     {
          if (U[poz1[p2]]>U[poz1[p1]])
             aux=poz1[p1], poz1[p1]=poz1[p2], poz1[p2]=aux;
     }
     else
     if (p2-p1>1)
     {
          sortu(p1,(p1+p2)>>1);
          sortu(((p1+p2)>>1)+1,p2);
        
          k = p1-1;
          i = p1;
          m = (p1+p2)>>1;
          j = m+1;
        
          while (i<=m && j<=p2)
          {
            k++;
        
            if (U[poz1[i]]>U[poz1[j]])
            {
              poz2[k] = poz1[i];
              i++;
            }
            else
            {
              poz2[k] = poz1[j];
              j++;
            }
          }
        
          if (i <= m)
          {
            for (j=i;j<=m;j++)
            {
              k++;
              poz2[k] = poz1[j];
            }
          }
          else
          {
            for (i=j;i <= p2;i++)
              {
              k++;
              poz2[k] = poz1[i];
              }
          }
        
          for (k = p1; k <= p2; k++) poz1[k] = poz2[k];
     }
}

double area(int a, int b, int c)
{
        double x1 = X[a], x2 = X[b], x3 = X[c];
        double y1 = Y[a], y2 = Y[b], y3 = Y[c];
        double s = x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3;
        return (fabs(s)*0.5);
}

int main()
{
        int val, i, j, k, p, x, y, z, np;
        double pi=2*acos(0), rez, a, b, c, sup;

        freopen("popandai.in","r",stdin);
        scanf("%d%d",&N,&K);

        for (i = 0; i < N; i++)
            scanf("%d %d", &X[i], &Y[i]);

       for (i = 0; i < N; i++) poz1[i]=i;
       sortx(0,N-1);
       for (i = 0; i < NMAX; i++)
           for (j = 0; j < NMAX; j++) A[i][j] = 0;
       
       for (i = 2; i < N; i++)
       {
         for (j = 0; j < i; j++)
         {
           U[poz1[j]]=atan2(Y[poz1[j]]-Y[poz1[i]],X[poz1[j]]-X[poz1[i]]);
           if ( U[poz1[j]] < eps) U[poz1[j]]+=2*pi;
         }
         sortu(0,i-1);
         for (j = 1; j < i; j++)
           if (X[poz1[j]]<X[poz1[j-1]])
              A[poz1[j]][poz1[i]]=A[poz1[j-1]][poz1[i]]+A[poz1[j]][poz1[j-1]]+1;
           else
              A[poz1[j]][poz1[i]]=A[poz1[j-1]][poz1[i]]-A[poz1[j-1]][poz1[j]];
       }

       Area = INF;
       for (x = 0; x < N; x++)
           for (y = x+1; y < N; y++)
           {
               for (z = 0; z < N; z++) Down[z] = Up[z] = INF;
               for (z = 0; z < N; z++)
                   if (x!=z&&y!=z)
                   {
                       i = x; j = y; k = z;
                       if (X[i] > X[j]) val = i, i = j, j = val;
                       if (X[i] > X[k]) val = i, i = k, k = val;
                       if (X[j] > X[k]) val = j, j = k, k = val;
                       a = Y[i]-Y[k];
                       b = X[k]-X[i];
                       c=(double)(X[i])*(double)(Y[k])-(double)(X[k])*(double)(Y[i]);
                       rez=a*X[j]+b*Y[j]+c;
                       if (rez > eps) { np = A[i][j]+A[j][k]-A[i][k];
                                        sup = area(i,j,k);
                                        if (sup-Up[np]<eps) Up[np] = sup; }
                       else { np = A[i][k]-A[i][j]-A[j][k]-1;
                              if (X[j]<=X[i]||X[j]>=X[k]) np++;
                              sup = area(i,j,k);
                              if (sup-Down[np]<eps) Down[np] = sup; }
                   }
               for (z = 0; z <= K; z++)
               {
                   sup = INF;
                   if ((Up[z]+Down[K-z])<INF) sup = Up[x]+Down[K-z];
                   if ((Up[K-z]+Down[z])<INF)
                      if ( (Up[K-z]+Down[z]-sup) < eps ) sup = Up[K-z]+Down[z];
                   if ( (sup-Area) < eps ) Area = sup;
               }
            }

       freopen("popandai.out", "w", stdout);
       printf("%lf\n", Area);
            
       return 0;

}