Cod sursa(job #88826)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 4 octombrie 2007 12:12:02
Problema Popandai Scor 8
Compilator c Status done
Runda Arhiva de probleme Marime 3.04 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], A[NMAX][NMAX];
int N, K;
double U[NMAX], Area, Up[NMAX], Down[NMAX];

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, x1, x2, x3, y1, y2, y3;
        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++)
            for (j = i+1; j < N; j++)
                if ( (X[i]>X[j])||(X[i]==X[j]&&Y[i]>Y[j]) )
                   val = X[i], X[i] = X[j], X[j] = val,
                   val = Y[i], Y[i] = Y[j], Y[j] = val;

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                for (k = 0; k < N; k++)
                {
                       x1 = X[k]; x2 = X[i]; x3 = X[j];
                       y1 = Y[k]; y2 = Y[i]; y3 = Y[j];
                       rez=(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-x1*y3);
                       if (rez < -eps)
                          if (X[k]>X[i]&&X[k]<X[j]) A[i][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;

}